| Message ID | 20231112120817.2635864-2-lehua.ding@rivai.ai |
|---|---|
| State | New |
| Headers | show |
| Series | ira/lra: Support subreg coalesce | expand |
On 11/12/23 07:08, Lehua Ding wrote: > 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: > I am not a maintainer or reviewer of data-flow analysis framework and can not approve this patch except changes in regs.h. Richard Sandiford or Jeff Law as global reviewers probably can do this. As for regs.h changes, they are ok for me after fixing general issues I mentioned in my previous email (two spaces after sentence ends in the comments). I think all this code is a major compiler time and memory consumer in all set of the patches. DF analysis is slow by itself even when only effective data structures as bitmaps are used but you are introducing even slower data structure as maps (I believe better performance data structure can be used instead). In the very first version of LRA I used DFA but it made LRA so slow that I had to introduce own data structures which are faster in case of massive RTL changes in LRA. The same problem exists for using generic C++ standard library data as vectors and maps for critical code. It is hard to get a needed performance when the exact implementation can vary or be not what you need, e.g. vector initial capacity, growth etc. But again the performance issues can be addressed later.
On Mon, Nov 13, 2023 at 11:39 PM Vladimir Makarov <vmakarov@redhat.com> wrote: > > > On 11/12/23 07:08, Lehua Ding wrote: > > 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: > > > I am not a maintainer or reviewer of data-flow analysis framework and > can not approve this patch except changes in regs.h. Richard Sandiford > or Jeff Law as global reviewers probably can do this. > > As for regs.h changes, they are ok for me after fixing general issues I > mentioned in my previous email (two spaces after sentence ends in the > comments). > > I think all this code is a major compiler time and memory consumer in > all set of the patches. DF analysis is slow by itself even when only > effective data structures as bitmaps are used but you are introducing > even slower data structure as maps (I believe better performance data > structure can be used instead). In the very first version of LRA I used > DFA but it made LRA so slow that I had to introduce own data structures > which are faster in case of massive RTL changes in LRA. The same > problem exists for using generic C++ standard library data as vectors > and maps for critical code. It is hard to get a needed performance when > the exact implementation can vary or be not what you need, e.g. vector > initial capacity, growth etc. But again the performance issues can be > addressed later. I think the important bit should be the subreg live analysis should be opt-in and when not enabled shouldn't have a bad effect on memory usage and compile-time. At -O0 and -O1 RA consumes a major amount of compile-time. Richard. >
On 2023/11/14 16:14, Richard Biener wrote: > On Mon, Nov 13, 2023 at 11:39 PM Vladimir Makarov <vmakarov@redhat.com> wrote: >> >> >> On 11/12/23 07:08, Lehua Ding wrote: >>> 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: >>> >> I am not a maintainer or reviewer of data-flow analysis framework and >> can not approve this patch except changes in regs.h. Richard Sandiford >> or Jeff Law as global reviewers probably can do this. >> >> As for regs.h changes, they are ok for me after fixing general issues I >> mentioned in my previous email (two spaces after sentence ends in the >> comments). >> >> I think all this code is a major compiler time and memory consumer in >> all set of the patches. DF analysis is slow by itself even when only >> effective data structures as bitmaps are used but you are introducing >> even slower data structure as maps (I believe better performance data >> structure can be used instead). In the very first version of LRA I used >> DFA but it made LRA so slow that I had to introduce own data structures >> which are faster in case of massive RTL changes in LRA. The same >> problem exists for using generic C++ standard library data as vectors >> and maps for critical code. It is hard to get a needed performance when >> the exact implementation can vary or be not what you need, e.g. vector >> initial capacity, growth etc. But again the performance issues can be >> addressed later. > > I think the important bit should be the subreg live analysis should be > opt-in and when not enabled shouldn't have a bad effect on memory > usage and compile-time. At -O0 and -O1 RA consumes a major > amount of compile-time. This is perfectly fine, the code inside the live_subreg problem has a branch that goes through similar logic to live_reg if it finds no subreg inside the program. Then when the optimization level is less than 2, it doesn't track the subreg. By the way, I'd like to ask you if you have certain programs where RA has a big impact on compilation time to offer? Or any suggestions about it?
On Tue, Nov 14, 2023 at 9:38 AM Lehua Ding <lehua.ding@rivai.ai> wrote: > > > > On 2023/11/14 16:14, Richard Biener wrote: > > On Mon, Nov 13, 2023 at 11:39 PM Vladimir Makarov <vmakarov@redhat.com> wrote: > >> > >> > >> On 11/12/23 07:08, Lehua Ding wrote: > >>> 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: > >>> > >> I am not a maintainer or reviewer of data-flow analysis framework and > >> can not approve this patch except changes in regs.h. Richard Sandiford > >> or Jeff Law as global reviewers probably can do this. > >> > >> As for regs.h changes, they are ok for me after fixing general issues I > >> mentioned in my previous email (two spaces after sentence ends in the > >> comments). > >> > >> I think all this code is a major compiler time and memory consumer in > >> all set of the patches. DF analysis is slow by itself even when only > >> effective data structures as bitmaps are used but you are introducing > >> even slower data structure as maps (I believe better performance data > >> structure can be used instead). In the very first version of LRA I used > >> DFA but it made LRA so slow that I had to introduce own data structures > >> which are faster in case of massive RTL changes in LRA. The same > >> problem exists for using generic C++ standard library data as vectors > >> and maps for critical code. It is hard to get a needed performance when > >> the exact implementation can vary or be not what you need, e.g. vector > >> initial capacity, growth etc. But again the performance issues can be > >> addressed later. > > > > I think the important bit should be the subreg live analysis should be > > opt-in and when not enabled shouldn't have a bad effect on memory > > usage and compile-time. At -O0 and -O1 RA consumes a major > > amount of compile-time. > > This is perfectly fine, the code inside the live_subreg problem has a > branch that goes through similar logic to live_reg if it finds no subreg > inside the program. Then when the optimization level is less than 2, it > doesn't track the subreg. By the way, I'd like to ask you if you have > certain programs where RA has a big impact on compilation time to offer? > Or any suggestions about it? I suggest you farm bugzilla for the compile-time-hog / memory-hog testcases. I do have a set of "large" testcases. Scanning results points at PRs 36262, 37448, 39326, 69609 all having RA in the 20% area at -O0 -g. It's also a good idea to take say cc1files (set of preprocessed sources that produce GCCs cc1) and look at the overall impact of compile-time and memory-usage of a change on those which are representative for "normal" TUs as opposed to the PRs above which often are large machine-generated TUs (an important area where GCC usually shines, at least at -O1). Richard. > -- > Best, > Lehua (RiVAI) > lehua.ding@rivai.ai
On 11/14/23 04:03, Richard Biener wrote: > > I suggest you farm bugzilla for the compile-time-hog / memory-hog testcases. > I do have a set of "large" testcases. Scanning results points at > PRs 36262, 37448, 39326, 69609 all having RA in the 20% area at > -O0 -g. > > It's also a good idea to take say cc1files (set of preprocessed sources > that produce GCCs cc1) and look at the overall impact of compile-time > and memory-usage of a change on those which are representative > for "normal" TUs as opposed to the PRs above which often are > large machine-generated TUs (an important area where GCC usually > shines, at least at -O1). > RA is expensive optimization pass in any compiler even if the fastest algorithms are used. The most illustrative PR for this is 108500 where RA at -O0 spent 90% (200s) of compilation time. But it is nothing in comparison with LLVM "fast" RA algorithm where LLVM-14 spent almost 100% or 41500s (200 times more than GCC) at -O0. LLVM greedy RA is even worse I stopped LLVM after 120hours at -O1 when GCC spent 30min at -O1. In contrast to LLVM, GCC RA also solves code selection task. IMHO GCC is better scaling compiler and better compiler for big TUs and functions. When I worked on CRuby, I saw an interesting results of GCC vs LLVM. Clang-15 with -O3 produced 70% slower (on a simple Ruby test) Ruby basic interpreter code than GCC-12 with -O3. Also Clang spends 20 times more time to compile major Ruby interpreter file vm.c with huge major interpreter function (315s for clang vs 15s for GCC).
On 11/14/23 03:38, Lehua Ding wrote: > > > This is perfectly fine, the code inside the live_subreg problem has a > branch that goes through similar logic to live_reg if it finds no > subreg inside the program. Then when the optimization level is less > than 2, it doesn't track the subreg. By the way, I'd like to ask you > if you have certain programs where RA has a big impact on compilation > time to offer? Or any suggestions about it? > I've analyzed effect of your patches to -O2 compilation time on compilation of some old version of combine.c. The total GCC compilation time increased by about 3%. I used x86_64 release mode compiler. Here are my more detail findings: RA compile time increased by 43%. 54% of this increase is due df_analyze time increase and 38% is due to overall ira_color increase (assign_hard_reg execution time increased in 50 times but still such big increase is 1/3 of overall ira_color increase). The rest (about 10%) of overall RA increase is mostly LRA increase due to lra_create_live_ranges. To see where 6% GCC compilation time increase on SPEC2017 is spent would be more interesting but it needs a lot of time for analysis.
On 11/14/23 12:18, Vladimir Makarov wrote: > > On 11/14/23 03:38, Lehua Ding wrote: >> >> >> This is perfectly fine, the code inside the live_subreg problem has a >> branch that goes through similar logic to live_reg if it finds no >> subreg inside the program. Then when the optimization level is less >> than 2, it doesn't track the subreg. By the way, I'd like to ask you >> if you have certain programs where RA has a big impact on compilation >> time to offer? Or any suggestions about it? >> > I've analyzed effect of your patches to -O2 compilation time on > compilation of some old version of combine.c. The total GCC > compilation time increased by about 3%. I used x86_64 release mode > compiler. Here are my more detail findings: > > RA compile time increased by 43%. > > 54% of this increase is due df_analyze time increase and 38% is due to > overall ira_color increase (assign_hard_reg execution time increased > in 50 times but still such big increase is 1/3 of overall ira_color > increase). > Sorry, due to different inlining of assign_hard_reg I reported wrong numbers for this function (for version w/o patches only assigning on the region border was taken), the compilation times for this function is basically the same. > The rest (about 10%) of overall RA increase is mostly LRA increase due > to lra_create_live_ranges. > > To see where 6% GCC compilation time increase on SPEC2017 is spent > would be more interesting but it needs a lot of time for analysis. > >
Lehua Ding <lehua.ding@rivai.ai> writes: > 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; I haven't fully processed the patch yet, sorry. And I think I might be about to cover things that you dealt with elsewhere. My assumption going into this was that a subreg liveness tracker would work as follows: - First we would work out which registers need to have subreg tracking. This could be done ahead of time by iterating over regno_reg_rtx. The condition in need_track_subreg looks like the correct one. For every other register, subreg liveness degenerates to the existing liveness problems. Such registers can be ignored. - We would assign a unique identifier to each subreg that we want to track, with subregs for the same register being consecutive. - There would be a mapping from pseudo registers to the first subreg that we want to track. The mapping would probably just be a linear array, but perhaps there are times when something more compact is appropriate. - The dataflow problem itself would then be very similar to the existing ones. But rather than computing bitmaps with a single bit per register, we'd be computing bitmaps that have N bits for N-register pseudos (and no bits for single-register pseudos). - There would be helper functions that consumers could use to iterate over a block. E.g. for a backwards walk over a block, a consumer would start with the bitmap of live-out subregs. It would then use these helper functions to keep the values up-to-date as it moves up through the block. That's done for normal liveness via the df_simulate_* helpers. But now that the codebase is C++, it might be more convenient for the subreg code to provide classes for walking a block. That should be relatively compile-time-friendly, although I agree with Vlad of course that DF does have efficiency problems. The nature of the way it works makes it at least O(#blocks * #regs). Did you consider doing it that way? Or does it not provide the information that you need? Thanks, Richard > 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<HARD_REG_SET> 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<HARD_REG_SET> 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 > + <http://www.gnu.org/licenses/>. */ > + > +#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<subreg_range> 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 > + <http://www.gnu.org/licenses/>. */ > + > +#ifndef GCC_SUBREG_LIVE_RANGE_H > +#define GCC_SUBREG_LIVE_RANGE_H > + > +#include "config.h" > +#include "system.h" > +#include "coretypes.h" > +#include <set> > +#include <map> > + > +/* 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<subreg_range> 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<unsigned int, subreg_ranges> 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<int, live_point> 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<int, live_points> subreg_points; > + std::map<int, int> last_start_points; > + std::map<int, subreg_ranges> 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")
Hi Richard, On 2023/11/21 4:11, Richard Sandiford wrote: > Lehua Ding <lehua.ding@rivai.ai> writes: >> 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; > > I haven't fully processed the patch yet, sorry. And I think I might be > about to cover things that you dealt with elsewhere. > > My assumption going into this was that a subreg liveness tracker would > work as follows: > > - First we would work out which registers need to have subreg tracking. > This could be done ahead of time by iterating over regno_reg_rtx. > The condition in need_track_subreg looks like the correct one. > > For every other register, subreg liveness degenerates to the existing > liveness problems. Such registers can be ignored. > > - We would assign a unique identifier to each subreg that we want to track, > with subregs for the same register being consecutive. > > - There would be a mapping from pseudo registers to the first subreg > that we want to track. The mapping would probably just be a linear > array, but perhaps there are times when something more compact is > appropriate. > > - The dataflow problem itself would then be very similar to the existing > ones. But rather than computing bitmaps with a single bit per register, > we'd be computing bitmaps that have N bits for N-register pseudos > (and no bits for single-register pseudos). > > - There would be helper functions that consumers could use to iterate > over a block. E.g. for a backwards walk over a block, a consumer > would start with the bitmap of live-out subregs. It would then use > these helper functions to keep the values up-to-date as it moves > up through the block. > > That's done for normal liveness via the df_simulate_* helpers. > But now that the codebase is C++, it might be more convenient for > the subreg code to provide classes for walking a block. > > That should be relatively compile-time-friendly, although I agree > with Vlad of course that DF does have efficiency problems. The nature > of the way it works makes it at least O(#blocks * #regs). > > Did you consider doing it that way? Or does it not provide the > information that you need? Thanks for providing such detailed instructions, this looks like it should perform well. I'll give it a try and come back with any questions. > >> 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<HARD_REG_SET> 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<HARD_REG_SET> 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 >> + <http://www.gnu.org/licenses/>. */ >> + >> +#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<subreg_range> 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 >> + <http://www.gnu.org/licenses/>. */ >> + >> +#ifndef GCC_SUBREG_LIVE_RANGE_H >> +#define GCC_SUBREG_LIVE_RANGE_H >> + >> +#include "config.h" >> +#include "system.h" >> +#include "coretypes.h" >> +#include <set> >> +#include <map> >> + >> +/* 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<subreg_range> 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<unsigned int, subreg_ranges> 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<int, live_point> 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<int, live_points> subreg_points; >> + std::map<int, int> last_start_points; >> + std::map<int, subreg_ranges> 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") >
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<HARD_REG_SET> 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<HARD_REG_SET> 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 + <http://www.gnu.org/licenses/>. */ + +#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<subreg_range> 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 + <http://www.gnu.org/licenses/>. */ + +#ifndef GCC_SUBREG_LIVE_RANGE_H +#define GCC_SUBREG_LIVE_RANGE_H + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include <set> +#include <map> + +/* 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<subreg_range> 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<unsigned int, subreg_ranges> 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<int, live_point> 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<int, live_points> subreg_points; + std::map<int, int> last_start_points; + std::map<int, subreg_ranges> 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")