From patchwork Sun Nov 12 12:08:11 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lehua Ding X-Patchwork-Id: 1862834 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4SSrv92DmGz1yRX for ; Sun, 12 Nov 2023 23:08:53 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 532E3385AC26 for ; Sun, 12 Nov 2023 12:08:48 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtpbguseast2.qq.com (smtpbguseast2.qq.com [54.204.34.130]) by sourceware.org (Postfix) with ESMTPS id 6BA643858D20 for ; Sun, 12 Nov 2023 12:08:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6BA643858D20 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 6BA643858D20 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=54.204.34.130 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699790914; cv=none; b=WI9dEVQZ3ZJLBjA2rhvi/b0TgoVYZzw1zAoCZt+1WqXThhOk6gWH9DMhsEAo5VmIXTLhcPU4qCXxKPGrkdb2pcfAdLxo/1yjjNYPrdWWdR6T5Je4bHvLMj3E8ERM4Zk2eXkFDaH5uFdPaJYl0hSW9IA4I+Q4x72JNmMrukY+5xc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699790914; c=relaxed/simple; bh=gwDnO29oCTCroTfUj5utU4SmPYa+kJY8tZ/eX24oou8=; h=From:To:Subject:Date:Message-Id:MIME-Version; b=kjDHZ+s8AlkK48JZMnQjpe7xgwAtAlHTfeR0X04C0Av58/I/JP7Hi4kqyt+PkB6uZmPHGzwzlqZKakLFFAfRN1fSq4C0pb07OyMirqMoe42W2ldbZ+zXpUpC64hAjfrFR70I41MCYk9onKSgv+9Vtl9f0FEaIrFpYVJJELiPsxo= ARC-Authentication-Results: i=1; server2.sourceware.org X-QQ-mid: bizesmtp67t1699790902tukcf4zv Received: from rios-cad121.hadoop.rioslab.org ( [58.60.1.9]) by bizesmtp.qq.com (ESMTP) with id ; Sun, 12 Nov 2023 20:08:21 +0800 (CST) X-QQ-SSF: 01400000000000C0F000000A0000000 X-QQ-FEAT: 90EFqYDyPxDUhKIkBodKbIJDh0/REkwjRoibVNHZ1SZiIAJES6EFyekjlb/mn j4dhsR1WvcDOTvUw4yUsDMPX3AcG9elMFdKd9P91FB7MvGPB+jPGs2V2+GARwW9U+ovsXHF Kf4TASilwJq+ap86Zn9n+5zB8qnsI1AUXVqtgTxzAvtXT/jf5JR/+BTHmab6rku0pcBbN69 5IZonqNz836pN+thNzbc5POqg2a1Recs+azoKuhunqkQMfNx8hwRz5jujI5OQUQloMpfAWH hGDrWpPweet901dDCQRZ7iDUcacBLAx/f9NSts08QYHitstuFcIwOe/mAZc98N6HGuWCWbY rmCftI0Xfn7UVrMx5z+EUmS4/NMz8NQJgJEAJtIOrHI8I5tGoVYfEmgfgS0LeMIdXXlUNAc gOt51zHZh6k= X-QQ-GoodBg: 2 X-BIZMAIL-ID: 10724261287090423654 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 V3 1/7] df: Add DF_LIVE_SUBREG problem Date: Sun, 12 Nov 2023 20:08:11 +0800 Message-Id: <20231112120817.2635864-2-lehua.ding@rivai.ai> X-Mailer: git-send-email 2.36.3 In-Reply-To: <20231112120817.2635864-1-lehua.ding@rivai.ai> References: <20231112120817.2635864-1-lehua.ding@rivai.ai> MIME-Version: 1.0 X-QQ-SENDSIZE: 520 Feedback-ID: bizesmtp:rivai.ai:qybglogicsvrgz:qybglogicsvrgz6a-0 X-Spam-Status: No, score=-11.1 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_ASCII_DIVIDERS, KAM_DMARC_STATUS, KAM_SHORT, 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 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org This patch adds a live_subreg problem to extend the original live_reg to track the liveness of subreg. We will only try to trace speudo registers who's mode size is a multiple of nature size and eventually a small portion of the inside will appear to use subreg. With live_reg problem, live_subreg prbolem will have the following output. full_in/out mean the entire pesudo live in/out, partial_in/out mean the subregs of the pesudo are live in/out, and range_in/out indicates which part of the pesudo is live. all_in/out is the union of full_in/out and partial_in/out: bitmap_head all_in, full_in; bitmap_head all_out, full_out; bitmap_head partial_in; bitmap_head partial_out; subregs_live *range_in = NULL; subregs_live *range_out = NULL; gcc/ChangeLog: * Makefile.in: Add new object file. * df-problems.cc (struct df_live_subreg_problem_data): The data of the new live_subreg problem. (need_track_subreg): New function. (get_range): Ditto. (remove_subreg_range): Ditto. (add_subreg_range): Ditto. (df_live_subreg_free_bb_info): Ditto. (df_live_subreg_alloc): Ditto. (df_live_subreg_reset): Ditto. (df_live_subreg_bb_local_compute): Ditto. (df_live_subreg_local_compute): Ditto. (df_live_subreg_init): Ditto. (df_live_subreg_check_result): Ditto. (df_live_subreg_confluence_0): Ditto. (df_live_subreg_confluence_n): Ditto. (df_live_subreg_transfer_function): Ditto. (df_live_subreg_finalize): Ditto. (df_live_subreg_free): Ditto. (df_live_subreg_top_dump): Ditto. (df_live_subreg_bottom_dump): Ditto. (df_live_subreg_add_problem): Ditto. * df.h (enum df_problem_id): Add live_subreg id. (DF_LIVE_SUBREG_INFO): Data accessor. (DF_LIVE_SUBREG_IN): Ditto. (DF_LIVE_SUBREG_OUT): Ditto. (DF_LIVE_SUBREG_FULL_IN): Ditto. (DF_LIVE_SUBREG_FULL_OUT): Ditto. (DF_LIVE_SUBREG_PARTIAL_IN): Ditto. (DF_LIVE_SUBREG_PARTIAL_OUT): Ditto. (DF_LIVE_SUBREG_RANGE_IN): Ditto. (DF_LIVE_SUBREG_RANGE_OUT): Ditto. (class subregs_live): New class. (class basic_block_subreg_live_info): Ditto. (class df_live_subreg_bb_info): Ditto. (df_live_subreg): Ditto. (df_live_subreg_add_problem): Ditto. (df_live_subreg_finalize): Ditto. (class subreg_range): Ditto. (need_track_subreg): Ditto. (remove_subreg_range): Ditto. (add_subreg_range): Ditto. (df_live_subreg_get_bb_info): Ditto. * regs.h (get_nblocks): Helper function. * timevar.def (TV_DF_LIVE_SUBREG): New timevar. * subreg-live-range.cc: New file. * subreg-live-range.h: New file. --- gcc/Makefile.in | 1 + gcc/df-problems.cc | 889 ++++++++++++++++++++++++++++++++++++++- gcc/df.h | 67 +++ gcc/regs.h | 7 + gcc/subreg-live-range.cc | 628 +++++++++++++++++++++++++++ gcc/subreg-live-range.h | 333 +++++++++++++++ gcc/timevar.def | 1 + 7 files changed, 1925 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 29cec21c825..e4403b5a30c 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1675,6 +1675,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 d2cfaf7f50f..2585c762fd1 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,894 @@ df_lr_verify_transfer_functions (void) bitmap_clear (&all_blocks); } +/*---------------------------------------------------------------------------- + REGISTER AND SUBREG LIVES + Like DF_RL, but fine-grained tracking of subreg lifecycle. + ----------------------------------------------------------------------------*/ + +/* Private data used to verify the solution for this problem. */ +struct df_live_subreg_problem_data +{ + /* An obstack for the bitmaps we need for this problem. */ + bitmap_obstack live_subreg_bitmaps; + bool has_subreg_live_p; +}; + +/* Helper functions */ + +/* Return true if REGNO is a pseudo and MODE is a multil regs size. */ +bool +need_track_subreg (int regno, machine_mode reg_mode) +{ + 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) + && regno >= FIRST_PSEUDO_REGISTER; +} + +/* Return subreg_range of REF. */ +static subreg_range +get_range (df_ref ref) +{ + rtx reg = DF_REF_REAL_REG (ref); + machine_mode reg_mode = GET_MODE (reg); + + if (!read_modify_subreg_p (DF_REF_REG (ref))) + return subreg_range (0, get_nblocks (reg_mode)); + + rtx subreg = DF_REF_REG (ref); + 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); + + return subreg_range (subreg_start, subreg_start + subreg_nblocks); +} + +/* Remove REF from BB_INFO use. */ +void +remove_subreg_range (basic_block_subreg_live_info *bb_info, unsigned int regno, + machine_mode mode, const subreg_range &range) +{ + int max = get_nblocks (mode); + bitmap full = &bb_info->full_use; + bitmap partial = &bb_info->partial_use; + subregs_live *range_live = bb_info->range_use; + + if (!range.full_p (max)) + { + if (bitmap_bit_p (full, regno)) + { + bitmap_clear_bit (full, regno); + gcc_assert (!bitmap_bit_p (partial, regno)); + gcc_assert (range_live->empty_p (regno)); + subreg_ranges temp = subreg_ranges (max); + temp.make_full (); + temp.remove_range (max, range); + range_live->add_ranges (regno, temp); + bitmap_set_bit (partial, regno); + return; + } + else if (bitmap_bit_p (partial, regno)) + { + range_live->remove_range (regno, max, range); + if (range_live->empty_p (regno)) + bitmap_clear_bit (partial, regno); + } + } + else if (bitmap_bit_p (full, regno)) + { + bitmap_clear_bit (full, regno); + gcc_assert (!bitmap_bit_p (partial, regno)); + } + else if (bitmap_bit_p (partial, regno)) + { + bitmap_clear_bit (partial, regno); + range_live->remove_live (regno); + } +} + +/* Return true if ref is a tracked subreg access. */ +bool +remove_subreg_range (basic_block_subreg_live_info *bb_info, df_ref ref) +{ + unsigned int regno = DF_REF_REGNO (ref); + machine_mode mode = GET_MODE (DF_REF_REAL_REG (ref)); + bool subreg_p = read_modify_subreg_p (DF_REF_REG (ref)); + + if (need_track_subreg (regno, mode)) + { + remove_subreg_range (bb_info, regno, mode, get_range (ref)); + return subreg_p; + } + 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)); + return false; + } +} + +/* add REF to BB_INFO def/use. */ +void +add_subreg_range (basic_block_subreg_live_info *bb_info, unsigned int regno, + machine_mode mode, const subreg_range &range, bool is_def) +{ + int max = get_nblocks (mode); + bitmap full = is_def ? &bb_info->full_def : &bb_info->full_use; + 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; + + if (!range.full_p (max)) + { + if (bitmap_bit_p (full, regno)) + return; + range_live->add_range (regno, max, range); + if (range_live->full_p (regno)) + { + bitmap_set_bit (full, regno); + gcc_assert (bitmap_bit_p (partial, regno)); + bitmap_clear_bit (partial, regno); + range_live->remove_live (regno); + } + else if (!bitmap_bit_p (partial, regno)) + bitmap_set_bit (partial, regno); + } + else if (!bitmap_bit_p (full, regno)) + { + bitmap_set_bit (full, regno); + if (bitmap_bit_p (partial, regno)) + { + bitmap_clear_bit (partial, regno); + range_live->remove_live (regno); + } + } +} + +/* Return true if ref is a tracked subreg access. */ +bool +add_subreg_range (basic_block_subreg_live_info *bb_info, df_ref ref, + bool is_def) +{ + unsigned int regno = DF_REF_REGNO (ref); + machine_mode mode = GET_MODE (DF_REF_REAL_REG (ref)); + bool subreg_p = read_modify_subreg_p (DF_REF_REG (ref)); + + if (need_track_subreg (regno, mode)) + { + add_subreg_range (bb_info, regno, mode, get_range (ref), is_def); + return subreg_p; + } + 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)); + + if (is_def && DF_REF_FLAGS (ref) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)) + add_subreg_range (bb_info, ref, false); + return false; + } +} + +/* 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_def; + bb_info->range_def = NULL; + delete bb_info->range_use; + bb_info->range_use = NULL; + delete bb_info->range_in; + bb_info->range_in = NULL; + delete bb_info->range_out; + bb_info->range_out = NULL; + + bitmap_clear (&bb_info->full_use); + bitmap_clear (&bb_info->partial_use); + bitmap_clear (&bb_info->full_def); + bitmap_clear (&bb_info->partial_def); + 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); + problem_data->has_subreg_live_p = false; + } + + 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) + { + 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->full_use.obstack) + { + bitmap_clear (&bb_info->full_def); + bitmap_clear (&bb_info->partial_def); + bitmap_clear (&bb_info->full_use); + bitmap_clear (&bb_info->partial_use); + 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->full_def, + &problem_data->live_subreg_bitmaps); + bitmap_initialize (&bb_info->partial_def, + &problem_data->live_subreg_bitmaps); + bitmap_initialize (&bb_info->full_use, + &problem_data->live_subreg_bitmaps); + bitmap_initialize (&bb_info->partial_use, + &problem_data->live_subreg_bitmaps); + 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_def) + { + bb_info->range_def->clear (); + bb_info->range_use->clear (); + bb_info->range_in->clear (); + bb_info->range_out->clear (); + } + else + { + bb_info->range_def = new subregs_live (); + bb_info->range_use = new subregs_live (); + bb_info->range_in = new subregs_live (); + bb_info->range_out = new subregs_live (); + } + } + 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_bb_info *bb_info = df_live_subreg_get_bb_info (bb_index); + df_live_subreg_problem_data *problem_data + = (df_live_subreg_problem_data *) df_live_subreg->problem_data; + 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) + { + problem_data->has_subreg_live_p + |= add_subreg_range (bb_info, def, true); + problem_data->has_subreg_live_p |= remove_subreg_range (bb_info, def); + } + + /* Process the hardware registers that are always live. */ + 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) == 0) + problem_data->has_subreg_live_p |= add_subreg_range (bb_info, use); + + 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) + { + problem_data->has_subreg_live_p |= remove_subreg_range (bb_info, def); + problem_data->has_subreg_live_p + |= add_subreg_range (bb_info, def, true); + } + + FOR_EACH_INSN_INFO_USE (use, insn_info) + { + unsigned int regno = DF_REF_REGNO (use); + machine_mode mode = GET_MODE (DF_REF_REAL_REG (use)); + /* Ignore the use of SET_DEST which is (subreg (reg) offset). */ + if (need_track_subreg (regno, mode) + && DF_REF_FLAGS (use) & (DF_REF_READ_WRITE | DF_REF_SUBREG)) + continue; + problem_data->has_subreg_live_p |= add_subreg_range (bb_info, use); + } + } + + /* 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) + { + problem_data->has_subreg_live_p + |= add_subreg_range (bb_info, def, true); + problem_data->has_subreg_live_p |= remove_subreg_range (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) + problem_data->has_subreg_live_p |= add_subreg_range (bb_info, use); +#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. */ + class df_live_subreg_bb_info *bb_info + = df_live_subreg_get_bb_info (EXIT_BLOCK); + bitmap_copy (&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); + bitmap_copy (&bb_info->full_in, &bb_info->full_use); + bitmap_copy (&bb_info->partial_in, &bb_info->partial_use); + bb_info->range_in->copy_lives (*bb_info->range_use); + bitmap_clear (&bb_info->full_out); + bitmap_clear (&bb_info->partial_out); + bb_info->range_out->clear (); + } +} + +/* Check the result is golden. */ +static void +df_live_subreg_check_result (bitmap full, bitmap partial, + subregs_live *partial_live) +{ + unsigned int regno; + bitmap_iterator bi; + gcc_assert (!bitmap_intersect_p (full, partial)); + EXECUTE_IF_SET_IN_BITMAP (full, 0, regno, bi) + gcc_assert (partial_live->empty_p (regno)); + 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) +{ + df_live_subreg_problem_data *problem_data + = (df_live_subreg_problem_data *) df_live_subreg->problem_data; + 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); + + if (!problem_data->has_subreg_live_p) + { + 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); + return changed; + } + + /* If there has subreg live need be tracked. Calculation formula: + temp_full mean: + 1. partial in out/in, full in other in/out + 2. partial in out and in, and mrege range is full + temp_range mean: + the range of regno which partial live + src_bb_info->partial_out = (src_bb_info->partial_out | + dest_bb_info->partial_in) & ~temp_full + src_bb_info->range_out = copy(temp_range) + src_bb_info->full_out |= dest_bb_info->full_in | temp_full + */ + subregs_live temp_range; + temp_range.add_lives (*src_bb_info->range_out); + temp_range.add_lives (*dest_bb_info->range_in); + + bitmap_head temp_partial_all; + bitmap_initialize (&temp_partial_all, &bitmap_default_obstack); + bitmap_ior (&temp_partial_all, &src_bb_info->partial_out, + &dest_bb_info->partial_in); + + bitmap_head temp_full; + bitmap_initialize (&temp_full, &bitmap_default_obstack); + + /* Collect regno that become full after merge src_bb_info->partial_out + and dest_bb_info->partial_in. */ + unsigned int regno; + bitmap_iterator bi; + EXECUTE_IF_SET_IN_BITMAP (&temp_partial_all, FIRST_PSEUDO_REGISTER, regno, bi) + { + if (bitmap_bit_p (&src_bb_info->full_out, regno) + || bitmap_bit_p (&dest_bb_info->full_in, regno)) + { + bitmap_set_bit (&temp_full, regno); + temp_range.remove_live (regno); + continue; + } + else if (!bitmap_bit_p (&src_bb_info->partial_out, regno) + || !bitmap_bit_p (&dest_bb_info->partial_in, regno)) + continue; + + subreg_ranges temp = src_bb_info->range_out->lives.at (regno); + temp.add_ranges (dest_bb_info->range_in->lives.at (regno)); + if (temp.full_p ()) + { + bitmap_set_bit (&temp_full, regno); + temp_range.remove_live (regno); + } + } + + /* Calculating src_bb_info->partial_out and src_bb_info->range_out. */ + bool changed = bitmap_and_compl (&src_bb_info->partial_out, &temp_partial_all, + &temp_full); + changed |= src_bb_info->range_out->copy_lives (temp_range); + + /* Calculating src_bb_info->full_out. */ + bitmap_ior_into (&temp_full, &dest_bb_info->full_in); + + /* 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, &temp_full, + eh_kills); + } + else + changed |= bitmap_ior_into (&src_bb_info->full_out, &temp_full); + + changed |= bitmap_ior_into (&src_bb_info->full_out, &df->hardware_regs_used); + + bitmap_clear (&temp_full); + bitmap_clear (&temp_partial_all); + + df_live_subreg_check_result (&src_bb_info->full_out, + &src_bb_info->partial_out, + src_bb_info->range_out); + return changed; +} + +/* Transfer function. */ + +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); + df_live_subreg_problem_data *problem_data + = (df_live_subreg_problem_data *) df_live_subreg->problem_data; + if (!problem_data->has_subreg_live_p) + { + bitmap in = &bb_info->full_in; + bitmap out = &bb_info->full_out; + bitmap use = &bb_info->full_use; + bitmap def = &bb_info->full_def; + + return bitmap_ior_and_compl (in, use, out, def); + } + + /* If there has subreg live need be tracked, follow the bellow calculation + formula: + all_def = full_def | partial_def + temp_partial_out = ((full_out & partail_def) + | (partail_out & ~all_def) + | (partial_out remove partail_def not empty)) + & ~full_use + temp_partial_be_full = (temp_partial_out & partial_use) merge be full + full_in = full_use | full_out & ~all_def | temp_partial_be_full + partail_in = (temp_partial_out | partial_use) & ~temp_partial_be_full */ + unsigned int regno; + bitmap_iterator bi; + bool changed = false; + bitmap_head temp_partial_out; + bitmap_head temp_partial_be_full; + bitmap_head all_def; + subregs_live temp_range_out; + bitmap_initialize (&temp_partial_out, &bitmap_default_obstack); + bitmap_initialize (&temp_partial_be_full, &bitmap_default_obstack); + bitmap_initialize (&all_def, &bitmap_default_obstack); + + bitmap_ior (&all_def, &bb_info->full_def, &bb_info->partial_def); + + /* temp_partial_out = (full_out & partail_def) */ + bitmap_and (&temp_partial_out, &bb_info->full_out, &bb_info->partial_def); + EXECUTE_IF_SET_IN_BITMAP (&temp_partial_out, FIRST_PSEUDO_REGISTER, regno, bi) + { + subreg_ranges temp (bb_info->range_def->lives.at (regno).max); + temp.make_full (); + temp.remove_ranges (bb_info->range_def->lives.at (regno)); + temp_range_out.add_ranges (regno, temp); + } + + /* temp_partial_out |= (partail_out & ~all_def) */ + bitmap_ior_and_compl_into (&temp_partial_out, &bb_info->partial_out, + &all_def); + EXECUTE_IF_AND_COMPL_IN_BITMAP (&bb_info->partial_out, &all_def, + FIRST_PSEUDO_REGISTER, regno, bi) + { + temp_range_out.add_ranges (regno, bb_info->range_out->lives.at (regno)); + } + + /* temp_partial_out |= (partial_out remove partail_def not empty) */ + EXECUTE_IF_AND_IN_BITMAP (&bb_info->partial_out, &bb_info->partial_def, 0, + regno, bi) + { + subreg_ranges temp = bb_info->range_out->lives.at (regno); + temp.remove_ranges (bb_info->range_def->lives.at (regno)); + if (!temp.empty_p ()) + { + bitmap_set_bit (&temp_partial_out, regno); + temp_range_out.add_ranges (regno, temp); + } + } + + /* temp_partial_out = temp_partial_out & ~full_use */ + bitmap_and_compl_into (&temp_partial_out, &bb_info->full_use); + EXECUTE_IF_SET_IN_BITMAP (&bb_info->full_use, 0, regno, bi) + if (!temp_range_out.empty_p (regno)) + temp_range_out.remove_live (regno); + + /* temp_partial_be_full = (temp_partial_out & partial_use) merge become full + */ + temp_range_out.add_lives (*bb_info->range_use); + /* Remove all range which in partial_use and in full_out and not in all_def. + */ + EXECUTE_IF_SET_IN_BITMAP (&bb_info->full_out, 0, regno, bi) + if (!bitmap_bit_p (&all_def, regno) && !temp_range_out.empty_p (regno)) + temp_range_out.remove_live (regno); + + EXECUTE_IF_AND_IN_BITMAP (&temp_partial_out, &bb_info->partial_use, 0, regno, + bi) + { + subreg_ranges temp = temp_range_out.lives.at (regno); + temp.add_ranges (bb_info->range_use->lives.at (regno)); + if (temp.full_p ()) + { + bitmap_set_bit (&temp_partial_be_full, regno); + temp_range_out.remove_live (regno); + } + } + + /* Calculating full_in. */ + bitmap_ior_and_compl_into (&temp_partial_be_full, &bb_info->full_out, + &all_def); + changed |= bitmap_ior (&bb_info->full_in, &temp_partial_be_full, + &bb_info->full_use); + + /* Calculating partial_in and range_in. */ + bitmap_ior_into (&temp_partial_out, &bb_info->partial_use); + changed |= bitmap_and_compl (&bb_info->partial_in, &temp_partial_out, + &temp_partial_be_full); + changed |= bb_info->range_in->copy_lives (temp_range_out); + + bitmap_clear (&temp_partial_out); + bitmap_clear (&temp_partial_be_full); + bitmap_clear (&all_def); + + df_live_subreg_check_result (&bb_info->full_in, &bb_info->partial_in, + bb_info->range_in); + + return changed; +} + +/* Run the fast dce as a side effect of building LR. */ + +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); + } +} + +/* 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) + { + df_live_subreg->block_info_size = 0; + free (df_live_subreg->block_info); + df_live_subreg->block_info = NULL; + bitmap_obstack_release (&problem_data->live_subreg_bitmaps); + free (df_live_subreg->problem_data); + df_live_subreg->problem_data = 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); + 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, &bb_info->full_use); + fprintf (file, ";; subreg live partial use \t"); + df_print_regset (file, &bb_info->partial_use); + fprintf (file, ";; subreg live range use \t"); + bb_info->range_use->dump (file, ""); + + fprintf (file, "\n;; subreg live full def \t"); + df_print_regset (file, &bb_info->full_def); + fprintf (file, ";; subreg live partial def \t"); + df_print_regset (file, &bb_info->partial_def); + fprintf (file, ";; subreg live range def \t"); + 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) +{ + 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 402657a7076..50a6cf99863 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 Ranges and Live Subreg */ DF_LIVE, /* Live Registers & Uninitialized Registers */ DF_RD, /* Reaching Defs. */ DF_CHAIN, /* Def-Use and/or Use-Def Chains. */ @@ -619,6 +620,7 @@ public: #define DF_SCAN_BB_INFO(BB) (df_scan_get_bb_info ((BB)->index)) #define DF_RD_BB_INFO(BB) (df_rd_get_bb_info ((BB)->index)) #define DF_LR_BB_INFO(BB) (df_lr_get_bb_info ((BB)->index)) +#define DF_LIVE_SUBREG_INFO(BB) (df_live_subreg_get_bb_info ((BB)->index)) #define DF_LIVE_BB_INFO(BB) (df_live_get_bb_info ((BB)->index)) #define DF_WORD_LR_BB_INFO(BB) (df_word_lr_get_bb_info ((BB)->index)) #define DF_MD_BB_INFO(BB) (df_md_get_bb_info ((BB)->index)) @@ -632,6 +634,15 @@ public: #define DF_MIR_IN(BB) (&DF_MIR_BB_INFO (BB)->in) #define DF_MIR_OUT(BB) (&DF_MIR_BB_INFO (BB)->out) +#define DF_LIVE_SUBREG_IN(BB) (&DF_LIVE_SUBREG_INFO (BB)->all_in) +#define DF_LIVE_SUBREG_OUT(BB) (&DF_LIVE_SUBREG_INFO (BB)->all_out) +#define DF_LIVE_SUBREG_FULL_IN(BB) (&DF_LIVE_SUBREG_INFO (BB)->full_in) +#define DF_LIVE_SUBREG_FULL_OUT(BB) (&DF_LIVE_SUBREG_INFO (BB)->full_out) +#define DF_LIVE_SUBREG_PARTIAL_IN(BB) (&DF_LIVE_SUBREG_INFO (BB)->partial_in) +#define DF_LIVE_SUBREG_PARTIAL_OUT(BB) (&DF_LIVE_SUBREG_INFO (BB)->partial_out) +#define DF_LIVE_SUBREG_RANGE_IN(BB) (DF_LIVE_SUBREG_INFO (BB)->range_in) +#define DF_LIVE_SUBREG_RANGE_OUT(BB) (DF_LIVE_SUBREG_INFO (BB)->range_out) + /* These macros are used by passes that are not tolerant of uninitialized variables. This intolerance should eventually be fixed. */ @@ -878,6 +889,32 @@ public: bitmap_head out; /* At the bottom of the block. */ }; +class subregs_live; + +class basic_block_subreg_live_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 = NULL; + subregs_live *range_use = NULL; +}; + +/* Live registers and live ranges including specifial subreg. */ +class df_live_subreg_bb_info : public basic_block_subreg_live_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 = NULL; + subregs_live *range_out = NULL; +}; /* Uninitialized registers. All bitmaps are referenced by the register number. Anded results of the forwards and backward live @@ -946,6 +983,7 @@ extern class df_d *df; #define df_note (df->problems_by_index[DF_NOTE]) #define df_md (df->problems_by_index[DF_MD]) #define df_mir (df->problems_by_index[DF_MIR]) +#define df_live_subreg (df->problems_by_index[DF_LIVE_SUBREG]) /* This symbol turns on checking that each modification of the cfg has been identified to the appropriate df routines. It is not part of @@ -1031,6 +1069,25 @@ 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 (void); +extern void +df_live_subreg_finalize (bitmap all_blocks); +class subreg_range; +extern bool +need_track_subreg (int regno, machine_mode mode); +extern void +remove_subreg_range (basic_block_subreg_live_info *bb_info, unsigned int regno, + machine_mode mode, const subreg_range &range); +extern bool +remove_subreg_range (basic_block_subreg_live_info *bb_info, df_ref ref); +extern void +add_subreg_range (basic_block_subreg_live_info *bb_info, unsigned int regno, + machine_mode mode, const subreg_range &range, + bool is_def = false); +extern bool +add_subreg_range (basic_block_subreg_live_info *bb_info, df_ref ref, + bool is_def = false); extern void df_live_set_all_dirty (void); extern void df_chain_add_problem (unsigned int); extern void df_word_lr_add_problem (void); @@ -1124,6 +1181,16 @@ df_lr_get_bb_info (unsigned int index) return NULL; } +inline class 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; +} + inline class df_md_bb_info * df_md_get_bb_info (unsigned int index) { diff --git a/gcc/regs.h b/gcc/regs.h index aea093ed795..84c6bdb980c 100644 --- a/gcc/regs.h +++ b/gcc/regs.h @@ -389,4 +389,11 @@ 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 mode's natural + size. So, satisfy the following equation: + (nblocks - 1) * natural_size < GET_MODE_SIZE (mode) + <= nblocks * 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/subreg-live-range.cc b/gcc/subreg-live-range.cc new file mode 100644 index 00000000000..43a5eafedf1 --- /dev/null +++ b/gcc/subreg-live-range.cc @@ -0,0 +1,628 @@ +/* SUBREG live range track 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" +#include "selftest.h" +#include "print-rtl.h" + +/* class subreg_range */ +void +subreg_range::dump (FILE *file) const +{ + fprintf (file, "[%d, %d)", start, end); +} + +/* class subreg_ranges */ +bool +subreg_ranges::add_range (int max, const subreg_range &new_range) +{ + subreg_range range = new_range; + if (full_p ()) + return false; + else if (max == 1) + { + gcc_assert (range.start == 0 && range.end == 1); + make_full (); + return true; + } + + if (this->max == 1) + change_max (max); + + gcc_assert (this->max == max); + gcc_assert (range.start < range.end); + + bool changed = empty_p (); + auto it = ranges.begin (); + while (it != ranges.end ()) + { + const subreg_range &r = *it; + gcc_assert (r.start < r.end); + + /* The possible positional relationship of R and RANGE. + 1~5 means R.start's possible position relative to RANGE + A~G means R.end's possible position relative to RANGE + caseN means when R.start at N positon, the R.end can be in which + positions. + + RANGE.start RANGE.end + [ ) + | | + R.start 1 2 3 4 5 + R.end | | + case1 A B C D E + case2 | C D E + case3 | F D E + case4 | | E + case5 | | G + + */ + + /* R.start at 1 position. */ + if (r.start < range.start) + { + /* R.end at A position. That means R and RANGE do not overlap. */ + if (r.end < range.start) + it++; + /* R.end at B/C position. That means RANGE's left part overlap R's + right part. Expand RANGE.start to R.start and remove R. */ + else if (r.end < range.end) + { + changed = true; + range.start = r.start; + it = ranges.erase (it); + } + /* R.end at D/E position. That means R already contains RANGE, nothing + todo. */ + else + return false; + } + /* R.start at 2 position. */ + else if (r.start == range.start) + { + /* R.end at C/D position. That means RANGE contains R, remove R and + insert RANGE. */ + if (r.end < range.end) + { + changed = true; + it = ranges.erase (it); + } + /* R.end at E position. That means R already contains RANGE, nothing + todo. */ + else + return false; + } + /* R.start at 3 position. */ + else if (r.start > range.start && r.start < range.end) + { + /* R.end at F/D position. That means RANGE contains R, just remove R + and insert RANGE later. */ + if (r.end <= range.end) + { + changed = true; + it = ranges.erase (it); + } + /* R.end at E position. That means RANGE's right part overlap R's + left part. Expand RANGE.end to R.end and remove R. */ + else if (r.end > range.end) + { + changed = true; + range.end = r.end; + it = ranges.erase (it); + break; + } + } + /* R.start at 4 position and R.end at E position. That means RANGE and R + are adjacent and can be merged. */ + else if (r.start == range.end) + { + changed = true; + range.end = r.end; + it = ranges.erase (it); + } + /* R.start at 5 position and R.end at G position. That means R and RANGE + do not overlap. */ + else + break; + } + ranges.insert (range); + return changed; +} + +bool +subreg_ranges::remove_range (int max, const subreg_range &range) +{ + if (empty_p ()) + return false; + else if (max == 1) + { + gcc_assert (range.start == 0 && range.end == 1); + make_empty (); + return true; + } + + if (this->max == 1) + { + gcc_assert (full_p ()); + change_max (max); + } + gcc_assert (this->max == max); + gcc_assert (range.start < range.end); + + bool changed = false; + auto it = ranges.begin (); + std::set new_ranges; + while (it != ranges.end ()) + { + auto &r = *it; + gcc_assert (r.start < r.end); + + /* The possible positional relationship of R and RANGE. + 1~5 means R.start's possible position relative to RANGE + A~G means R.end's possible position relative to RANGE + caseN means when R.start at N positon, the R.end can be in which + positions. + + RANGE.start RANGE.end + [ ) + | | + R.start 1 2 3 4 5 + R.end | | + case1 A B C D E + case2 | C D E + case3 | F D E + case4 | | E + case5 | | G + + */ + + /* R.start at 1 position. */ + if (r.start < range.start) + { + /* R.end at A/B position. That means RANGE and R do not overlap, + nothing to remove. */ + if (r.end <= range.start) + it++; + /* R.end at C/D position. That means R's rigth part contains RANGE, + need shrink R.end to RANGE.start. */ + else if (r.end <= range.end) + { + changed = true; + new_ranges.insert (subreg_range (r.start, range.start)); + it = ranges.erase (it); + } + /* R.end at E position. That means R's center part contains RANGE, + need split R to two range, one range is [R.start, RANGE.start), + another range is [RANGE.end, R.end). */ + else + { + changed = true; + new_ranges.insert (subreg_range (r.start, range.start)); + new_ranges.insert (subreg_range (range.end, r.end)); + it = ranges.erase (it); + break; + } + } + /* R.start at 2 position. */ + else if (r.start == range.start) + { + /* R.end at C/D position. That means RANGE contains R, remove R. */ + if (r.end <= range.end) + { + changed = true; + it = ranges.erase (it); + } + /* R.end at E position. That means R's left part contains RANGE, + shrink R.start to RANGE.end. */ + else + { + changed = true; + new_ranges.insert (subreg_range (range.end, r.end)); + it = ranges.erase (it); + break; + } + } + /* R.start at 3 position. */ + else if (r.start > range.start && r.start < range.end) + { + /* R.end at F/D position. That means RANGE contains R, remove R. */ + if (r.end <= range.end) + { + changed = true; + it = ranges.erase (it); + } + /* R.end at E position. That means RANGE's right part overlap R's left + part, shrink R.start to RANGE.end. */ + else + { + changed = true; + new_ranges.insert (subreg_range (range.end, r.end)); + it = ranges.erase (it); + break; + } + } + /* R.start at 4/5 position. That means RANGE and R do not overlap. */ + else + break; + } + for (auto &r : new_ranges) + add_range (this->max, r); + return changed; +} + +bool +subreg_ranges::add_ranges (const subreg_ranges &sr) +{ + gcc_assert (max == sr.max || max == 1 || sr.max == 1); + + if (full_p () || sr.empty_p ()) + return false; + else if (sr.full_p ()) + { + make_full (); + return true; + } + + bool changed = false; + for (auto &r : sr.ranges) + changed |= add_range (sr.max, r); + return changed; +} + +bool +subreg_ranges::remove_ranges (const subreg_ranges &sr) +{ + if (empty_p () || sr.empty_p ()) + return false; + else if (sr.full_p ()) + { + make_empty (); + return true; + } + + gcc_assert (max == sr.max || max == 1 || sr.max == 1); + + bool changed = false; + for (auto &r : sr.ranges) + changed |= remove_range (sr.max, r); + return changed; +} + +bool +subreg_ranges::same_p (const subreg_ranges &sr) const +{ + if (max == 1 || sr.max == 1) + return (empty_p () && sr.empty_p ()) || (full_p () && sr.full_p ()); + else if (max == sr.max) + { + if (ranges.size () != sr.ranges.size ()) + return false; + /* Make sure that the elements in each position are the same. */ + auto it1 = ranges.begin (); + auto it2 = sr.ranges.begin (); + while (it1 != ranges.end ()) + { + const subreg_range &r1 = *it1; + const subreg_range &r2 = *it2; + if (r1.start != r2.start || r1.end != r2.end) + return false; + it1++; + it2++; + } + return true; + } + else + gcc_unreachable (); +} + +bool +subreg_ranges::include_ranges_p (const subreg_ranges &sr) const +{ + gcc_assert (max == sr.max || max == 1 || sr.max == 1); + if (full_p ()) + return true; + if (empty_p () && sr.empty_p ()) + return true; + if (same_p (sr)) + return true; + + for (const auto &r : sr.ranges) + if (!include_range_p (sr.max, r)) + return false; + return true; +} + +bool +subreg_ranges::include_range_p (int max, const subreg_range &range) const +{ + gcc_assert (this->max == max); + for (const auto &r : ranges) + { + if (r.start <= range.start && r.end >= range.end) + return true; + else if (r.start >= range.end) + return false; + } + return false; +} + +void +subreg_ranges::dump (FILE *file) const +{ + if (empty_p ()) + { + fprintf (file, "empty"); + return; + } + else if (full_p ()) + { + fprintf (file, "full"); + return; + } + + fprintf (file, "patial(max:%d", max); + fprintf (file, " {"); + for (auto &range : ranges) + { + fprintf (file, " "); + range.dump (file); + } + fprintf (file, " })"); +} + +/* class subregs_live */ +bool +subregs_live::copy_lives (const subregs_live &sl) +{ + bool changed = false; + subregs_live temp; + for (auto &kv : sl.lives) + { + unsigned int regno = kv.first; + const subreg_ranges &sr = kv.second; + if (lives.count (regno) == 0 && !sr.empty_p ()) + { + changed = true; + temp.add_ranges (regno, sr); + } + else if (lives.count (regno) != 0) + { + changed |= !lives.at (regno).same_p (sr); + temp.add_ranges (regno, sr); + } + } + + for (auto &kv : lives) + { + unsigned int regno = kv.first; + subreg_ranges &sr = kv.second; + if (temp.lives.count (regno) == 0 && !sr.empty_p ()) + changed = true; + } + lives = temp.lives; + return changed; +} + +bool +subregs_live::add_lives (const subregs_live &sl) +{ + bool changed = false; + for (auto &kv : sl.lives) + { + unsigned int regno = kv.first; + const subreg_ranges &sr = kv.second; + if (sr.empty_p ()) + continue; + + if (lives.count (regno) == 0) + { + changed = true; + lives.insert ({regno, sr}); + } + else + changed |= lives.at (regno).add_ranges (sr); + } + return changed; +} + +bool +subregs_live::remove_lives (const subregs_live &sl) +{ + bool changed = false; + for (auto &kv : sl.lives) + { + unsigned int regno = kv.first; + const subreg_ranges &sr = kv.second; + if (sr.empty_p ()) + continue; + + if (lives.count (regno) != 0) + { + changed |= lives.at (regno).remove_ranges (sr); + if (lives.at (regno).empty_p ()) + lives.erase (regno); + } + } + return changed; +} + +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 subreg_ranges &sr = kv.second; + if (sr.empty_p ()) + continue; + fprintf (file, "%d ", kv.first); + if (!sr.full_p ()) + { + sr.dump (file); + fprintf (file, " "); + } + } + fprintf (file, "\n"); +} + +/* class live_point */ +void +live_point::dump (FILE *file) const +{ + if (!use_reg.empty_p ()) + { + fprintf (file, "use "); + use_reg.dump (file); + if (!def_reg.empty_p ()) + { + fprintf (file, ", def "); + def_reg.dump (file); + } + } + else if (!def_reg.empty_p ()) + { + fprintf (file, "def "); + def_reg.dump (file); + } + else + gcc_unreachable (); +} + +/* class live_points */ +void +live_points::dump (FILE *file) const +{ + fprintf (file, "%u :", id); + if (points.empty ()) + { + fprintf (file, " empty"); + return; + } + for (const auto &kv : points) + { + fprintf (file, " "); + kv.second.dump (file); + fprintf (file, " at point %u;", kv.first); + } +} + +/* class reg_live_ranges */ +void +subregs_live_points::dump (FILE *file) const +{ + if (subreg_points.empty ()) + { + fprintf (file, ";; empty\n"); + return; + } + for (const auto &kv : subreg_points) + { + fprintf (file, ";; "); + kv.second.dump (file); + fprintf (file, "\n"); + } +} + +/* Define some usefull debug functions. */ + +DEBUG_FUNCTION void +debug (const subreg_range &r) +{ + r.dump (stderr); +} + +DEBUG_FUNCTION void +debug (const subreg_ranges &sr) +{ + sr.dump (stderr); +} + +DEBUG_FUNCTION void +debug (const subregs_live &l) +{ + l.dump (stderr, ""); +} + +DEBUG_FUNCTION void +debug (const subregs_live *l) +{ + debug (*l); +} + +DEBUG_FUNCTION void +debug (const live_point &l) +{ + l.dump (stderr); +} + +DEBUG_FUNCTION void +debug (const live_points &ls) +{ + ls.dump (stderr); +} + +DEBUG_FUNCTION void +debug (const subregs_live_points &sls) +{ + sls.dump (stderr); +} + +DEBUG_FUNCTION void +debug (const subregs_live_points *sls) +{ + debug (*sls); +} + +#if CHECKING_P + +namespace selftest { + +class subreg_range_tests +{ +public: + static void run () + { + /* class subreg_range tests. */ + subreg_range r1 = subreg_range (1, 2); + subreg_range r2 = subreg_range (2, 3); + subreg_range r3 = subreg_range (2, 3); + ASSERT_FALSE (r1.same_p (r2)); + ASSERT_TRUE (r2.same_p (r3)); + ASSERT_TRUE (r1 < r2); + ASSERT_FALSE (r2 < r1); + + /* class subreg_ranges tests. */ + } +}; + +void +subreg_live_range_tests () +{ + subreg_range_tests::run (); +} + +} // namespace selftest + +#endif /* CHECKING_P */ diff --git a/gcc/subreg-live-range.h b/gcc/subreg-live-range.h new file mode 100644 index 00000000000..76e442d08e8 --- /dev/null +++ b/gcc/subreg-live-range.h @@ -0,0 +1,333 @@ +/* SUBREG live range track 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 + +/* class subreg_range represent bytes range [start, end) of a reg. */ +class subreg_range +{ +public: + int start; /* Range start point. */ + int end; /* Range start point. */ + + subreg_range (int start, int end) : start (start), end (end) + { + gcc_assert (start < end); + } + + /* For sorting. */ + bool operator<(const subreg_range &r) const + { + if (end <= r.start) + return true; + else if (start >= r.end) + return false; + else + /* Cannot sorting for overlap range. */ + gcc_unreachable (); + } + /* Return true if R same with self. */ + bool same_p (const subreg_range &r) const + { + return start == r.start && end == r.end; + } + + /* Return true if range is full for 0-MAX range. */ + bool full_p (int max) const { return start == 0 && end == max; } + + /* Debug methods. */ + void dump (FILE *file) const; +}; + +/* class subreg_ranges represent multiple disjoint and discontinuous + subreg_range. */ +class subreg_ranges +{ +public: + /* The maximum boundary value of range. If for a unknown mode hard register, + the max set to 1. */ + int max; + std::set ranges; + + subreg_ranges () : max (1) {} + subreg_ranges (int max) : max (max) { gcc_assert (max >= 1); } + + /* Modify ranges. */ + /* Return true if ranges changed. */ + bool add_range (int max, const subreg_range &range); + /* Return true if ranges changed. */ + bool remove_range (int max, const subreg_range &range); + /* Add SR, return true if ranges changed. */ + bool add_ranges (const subreg_ranges &sr); + /* Clear ranges of SR, return true if ranges changed. */ + bool remove_ranges (const subreg_ranges &sr); + /* Make range empty. */ + void make_empty () { ranges.clear (); } + /* Make range full. */ + void make_full () + { + make_empty (); + ranges.insert (subreg_range (0, max)); + } + /* Change max to MAX, corresponding adjust ranges. */ + void change_max (int max) + { + gcc_assert (this->max == 1); + this->max = max; + if (full_p ()) + make_full (); + } + + /* Predicators. */ + bool full_p () const + { + if (ranges.size () != 1) + return false; + const subreg_range &r = *ranges.begin (); + return r.start == 0 && r.end == max; + } + bool empty_p () const { return ranges.empty (); } + bool same_p (const subreg_ranges &sr) const; + bool same_p (int max, const subreg_range &range) const + { + subreg_ranges sr = subreg_ranges (max); + sr.add_range (max, range); + return same_p (sr); + } + bool include_ranges_p (const subreg_ranges &sr) const; + bool include_range_p (int max, const subreg_range &range) const; + + /* Debug methods. */ + void dump (FILE *file) const; +}; + +/* class subregs_live record the live subreg_ranges of registers. */ +class subregs_live +{ +public: + /* The key is usually the register's regno. */ + std::map lives; + + /* Add/clear live range. */ + bool add_range (unsigned int regno, int max, const subreg_range &range) + { + if (lives.count (regno) == 0) + lives.insert ({regno, subreg_ranges (max)}); + return lives.at (regno).add_range (max, range); + } + bool remove_range (unsigned int regno, int max, const subreg_range &range) + { + if (lives.count (regno) != 0) + { + bool changed = lives.at (regno).remove_range (max, range); + if (lives.at (regno).empty_p ()) + remove_live (regno); + return changed; + } + return false; + } + /* Add a unexist register live range. */ + void add_ranges (unsigned int regno, const subreg_ranges &ranges) + { + if (lives.count (regno) == 0) + lives.insert ({regno, ranges}); + else + lives.at (regno).add_ranges (ranges); + } + bool copy_lives (const subregs_live &sl); + bool add_lives (const subregs_live &sl); + bool remove_lives (const subregs_live &sl); + void remove_live (unsigned int regno) { lives.erase (regno); } + /* Remove all register live range. */ + void clear () { lives.clear (); } + void clear (unsigned min_regno) + { + if (lives.lower_bound (min_regno) != lives.end ()) + lives.erase (lives.lower_bound (min_regno), lives.end ()); + } + + /* Return true if regno's live range is full. */ + bool full_p (unsigned int regno) const + { + return lives.count (regno) != 0 && lives.at (regno).full_p (); + } + /* Return true if regno's live range is empty. */ + bool empty_p (unsigned int regno) const + { + return lives.count (regno) == 0 || lives.at (regno).empty_p (); + } + /* Return true if SL same with this. */ + bool same_p (const subregs_live &sl) + { + if (lives.size () != sl.lives.size ()) + return false; + for (auto &kv : lives) + { + unsigned int regno = kv.first; + if (sl.empty_p (regno)) + return false; + const subreg_ranges &sr = kv.second; + if (!sr.same_p (sl.lives.at (regno))) + return false; + } + return true; + } + + /* Debug methods. */ + void dump (FILE *file, const char *indent = ";; ") const; +}; + +class live_point +{ +public: + int point; + /* subreg range be defined in current point. */ + subreg_ranges def_reg; + /* subreg range be used in current point. */ + subreg_ranges use_reg; + + live_point (int max, const subreg_range &range, bool is_def) + : def_reg (max), use_reg (max) + { + add_range (max, range, is_def); + } + live_point (const subreg_ranges &sr, bool is_def) + : def_reg (sr.max), use_reg (sr.max) + { + add_ranges (sr, is_def); + } + live_point (int point, int max) : point (point), def_reg (max), use_reg (max) + {} + + void add_range (int max, const subreg_range &r, bool is_def) + { + if (is_def) + def_reg.add_range (max, r); + else + use_reg.add_range (max, r); + } + + void add_ranges (const subreg_ranges &sr, bool is_def) + { + if (is_def) + def_reg.add_ranges (sr); + else + use_reg.add_ranges (sr); + } + + void dump (FILE *file) const; +}; + +class live_points +{ +public: + int id; + int max; + std::map points; + + live_points (int id, int max) : id (id), max (max) {} + + void add_point (int max, const subreg_range &range, bool is_def, int point) + { + gcc_assert (this->max == max || this->max == 1 || max == 1); + if (points.count (point) == 0) + points.insert ({point, {max, range, is_def}}); + else + points.at (point).add_range (max, range, is_def); + } + void dump (FILE *file) const; +}; + +class subregs_live_points +{ +public: + std::map subreg_points; + std::map last_start_points; + std::map subreg_live_ranges; + + void add_point (int id, int max, const subreg_range &range, bool is_def, + int point) + { + if (!is_def && empty_live_p (id)) + { + if (last_start_points.count (id) == 0) + last_start_points.insert ({id, point}); + else + last_start_points.at (id) = point; + } + + if (subreg_points.count (id) == 0) + subreg_points.insert ({id, live_points (id, max)}); + + subreg_points.at (id).add_point (max, range, is_def, point); + + if (subreg_live_ranges.count (id) == 0) + subreg_live_ranges.insert ({id, subreg_ranges (max)}); + + if (is_def) + subreg_live_ranges.at (id).remove_range (max, range); + else + subreg_live_ranges.at (id).add_range (max, range); + } + + void add_range (int id, int max, const subreg_range &range, bool is_def) + { + if (subreg_live_ranges.count (id) == 0) + subreg_live_ranges.insert ({id, subreg_ranges (max)}); + + if (is_def) + subreg_live_ranges.at (id).remove_range (max, range); + else + subreg_live_ranges.at (id).add_range (max, range); + } + + bool full_live_p (int id) + { + return subreg_live_ranges.count (id) != 0 + && subreg_live_ranges.at (id).full_p (); + } + + bool empty_live_p (int id) + { + return subreg_live_ranges.count (id) == 0 + || subreg_live_ranges.at (id).empty_p (); + } + + int get_start_point (int id) + { + int start_point = last_start_points.at (id); + gcc_assert (start_point != -1); + return start_point; + } + + void clear_live_ranges () { subreg_live_ranges.clear (); } + + /* Debug methods. */ + void dump (FILE *file) const; +}; + +#endif /* GCC_SUBREG_LIVE_RANGE_H */ diff --git a/gcc/timevar.def b/gcc/timevar.def index d21b08c030d..7c173d3c7c8 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")