Re: Add "fast" conversions from arrays to bitmaps

[Jeff Law <law at redhat dot com>]

On 9/9/19 10:32 AM, Richard Sandiford wrote:
> This patch adds a bitmap_view<X> class that creates a read-only,
> on-stack bitmap representation of an array-like object X.  The main
> use case is to allow HARD_REG_SETs to be used in REG_SET (i.e. bitmap)
> operations.
> 
> For now it only handles constant-sized arrays, but I've tried to
> define the types in a way that could handle variable-sized arrays
> in future (although less efficiently).  E.g. this might be useful
> for combining bitmaps and sbitmaps.
> 
> For the read-only view to work as intended, I needed to make
> bitmap_bit_p take a const_bitmap instead of a bitmap.  Logically
> the bitmap really is read-only, but we update the "current" and
> "indx" fields of the bitmap_head after doing a search.
> 
> The patch makes this change using a const_cast.  Another option
> was to make the fields mutable and push the constness down to
> bitmap_list_find_element and bitmap_tree_find_element.
> However, the constness of const_bitmap should apply to the bitmap
> as a whole rather than just the head structure, so if the input
> to those functions is a const_bitmap, the result should be a
> "const bitmap_element *".  We'd therefore need overloaded versions of
> bitmap_*_find_element that take a constant bitmap and return a constant
> element (as for standard container accessors).  These would be wrappers
> around the non-constant versions and themselves need a const_cast.
> All that seemed a bit over-the-top for an internal interface.
> 
> I experimented with a few ways of writing the constructors, but the
> attached gave the best code.  E.g. (for x86_64 users):
> 
> void
> foo (bitmap a, const_hard_reg_set b)
> {
>   bitmap_ior_into (a, bitmap_view<HARD_REG_SET> (b));
> }
> 
> becomes:
> 
>         .cfi_startproc
>         subq    $88, %rsp
>         .cfi_def_cfa_offset 96
>         movq    (%rsi), %rdx
>         movq    8(%rsi), %rax
>         movq    $0, (%rsp)
>         movq    $0, 8(%rsp)
>         movq    %rdx, %rcx
>         movq    $0, 16(%rsp)
>         orq     %rax, %rcx
>         movq    $0, 24(%rsp)
>         je      .L645
>         leaq    32(%rsp), %rcx
>         movl    $0, 48(%rsp)
>         movq    %rcx, 8(%rsp)
>         movq    $0, 40(%rsp)
>         movq    $0, 32(%rsp)
>         movq    %rcx, 16(%rsp)
>         movq    %rdx, 56(%rsp)
>         movq    %rax, 64(%rsp)
> .L645:
>         movq    %rsp, %rsi
>         call    _Z15bitmap_ior_intoP11bitmap_headPKS_
>         addq    $88, %rsp
>         .cfi_def_cfa_offset 8
>         ret
> 
> which ought to be more efficient than the loops that the patch
> is replacing.
> 
> Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?
> 
> Richard
> 
> 
> 2019-09-09  Richard Sandiford  <richard.sandiford@arm.com>
> 
> gcc/
> 	* array-traits.h: New file.
> 	* coretypes.h (array_traits, bitmap_view): New types.
> 	* bitmap.h: Include "array-traits.h"
> 	(bitmap_bit_p): Take a const_bitmap instead of a bitmap.
> 	(base_bitmap_view, bitmap_view): New classes.
> 	* bitmap.c (bitmap_bit_p): Take a const_bitmap instead of a bitmap.
> 	* hard-reg-set.h: Include array-traits.h.
> 	(array_traits<HARD_REG_SET>): New struct.
> 	* regset.h (IOR_REG_SET_HRS): New macro.
> 	* loop-iv.c (simplify_using_initial_values): Use IOR_REG_SET_HRS
> 	rather than iterating over each hard register.
> 	* sched-deps.c (sched_analyze_insn): Likewise.
> 	* sel-sched-ir.c (setup_id_implicit_regs): Likewise.
OK
jeff