_BitInt lowering support [PR102989]

_BitInt lowering support [PR102989]

The following patch adds a new bitintlower lowering pass which lowers most
operations on medium _BitInt into operations on corresponding integer types,
large _BitInt into straight line code operating on 2 or more limbs and
finally huge _BitInt into a loop plus optional straight line code.

As the only supported architecture is little-endian, the lowering only
supports little-endian for now, because it would be impossible to test it
all for big-endian.  Rest is written with any endian support in mind, but
of course only little-endian has been actually tested.
I hope it is ok to add big-endian support to the lowering pass incrementally
later when first big-endian target shows with the backend support.
There are 2 possibilities of adding such support, one would be minimal one,
just tweak limb_access function and perhaps one or two other spots and
transform there the indexes from little endian (index 0 is least significant)
to big endian for just the memory access.  Advantage is I think maintainance
costs, disadvantage is that the loops will still iterate from 0 to some number
of limbs and we'd rely on IVOPTs or something similar changing it later if
needed.  Or we could make those indexes endian related everywhere, though
I'm afraid that would be several hundreds of changes.

For switches indexed by large/huge _BitInt the patch invokes what the switch
lowering pass does (but only on those specific switches, not all of them);
the switch lowering breaks the switches into clusters and none of the clusters
can have a range which doesn't fit into 64-bit UWHI, everything else will be
turned into a tree of comparisons.  For clusters normally emitted as smaller
switches, because we already have a guarantee that the low .. high range is
at most 64 bits, the patch forces subtraction of the low and turns it into
a 64-bit switch.  This is done before the actual pass starts.
Similarly, we cancel lowering of certain constructs like ABS_EXPR, ABSU_EXPR,
MIN_EXPR, MAX_EXPR and COND_EXPR and turn those back to simpler comparisons
etc., so that fewer operations need to be lowered later.

2023-09-06  Jakub Jelinek  <jakub@redhat.com>

	PR c/102989
	* Makefile.in (OBJS): Add gimple-lower-bitint.o.
	* passes.def: Add pass_lower_bitint after pass_lower_complex and
	pass_lower_bitint_O0 after pass_lower_complex_O0.
	* tree-pass.h (PROP_gimple_lbitint): Define.
	(make_pass_lower_bitint_O0, make_pass_lower_bitint): Declare.
	* gimple-lower-bitint.h: New file.
	* tree-ssa-live.h (struct _var_map): Add bitint member.
	(init_var_map): Adjust declaration.
	(region_contains_p): Handle map->bitint like map->outofssa_p.
	* tree-ssa-live.cc (init_var_map): Add BITINT argument, initialize
	map->bitint and set map->outofssa_p to false if it is non-NULL.
	* tree-ssa-coalesce.cc: Include gimple-lower-bitint.h.
	(build_ssa_conflict_graph): Call build_bitint_stmt_ssa_conflicts if
	map->bitint.
	(create_coalesce_list_for_region): For map->bitint ignore SSA_NAMEs
	not in that bitmap, and allow res without default def.
	(compute_optimized_partition_bases): In map->bitint mode try hard to
	coalesce any SSA_NAMEs with the same size.
	(coalesce_bitint): New function.
	(coalesce_ssa_name): In map->bitint mode, or map->bitmap into
	used_in_copies and call coalesce_bitint.
	* gimple-lower-bitint.cc: New file.