patch to fix

[Kenneth Zadeck]

The enclosed patch is the third of at least four patches that fix the
problems associated with supporting integers on the target that are
wider than two HOST_WIDE_INTs.

While GCC claims to support OI mode, and we have two public ports that
make minor use of this mode, in practice, compilation that uses OImode
mode commonly gives the wrong result or ices.  We have a private port
of GCC for an architecture that is further down the road to needing
comprehensive OImode and we have discovered that this is unusable. We
have decided to fix it in a general way that so that it is most
beneficial to the GCC community.  It is our belief that we are just a
little ahead of the X86 and the NEON and these patches will shortly be
essential.

The first two of these patches were primarily lexigraphical and have
already been committed.    They transformed the uses of CONST_DOUBLE
so that it is easy to tell what the intended usage is.

The underlying structures in the next two patches are very general:
once they are added to the compiler, the compiler will be able to
support targets with any size of integer from hosts of any size
integer.

The patch enclosed deals with the portable RTL parts of the compiler.
The next patch, which is currently under construction deals with the
tree level.  However, this patch can be put on the trunk as is, and it
will eleviate many, but not all of the current limitations in the rtl
parts of the compiler.

Some of the patch is conditional, depending on a port defining the
symbol 'TARGET_SUPPORTS_WIDE_INT' to be non zero.  Defining this
symbol to be non zero is declaring that the port has been converted to
use the new form or integer constants.  However, the patch is
completely backwards compatible to allow ports that do not need this
immediately to convert at their leasure.  The conversion process is
not difficult, but it does require some knowledge of the port, so we
are not volinteering to do this for all ports.

OVERVIEW OF THE PATCH:

The patch defines a new datatype, a 'wide_int' (defined in
wide-int.[ch], and this datatype will be used to perform all of the
integer constant math in the compiler.  Externally, wide-int is very
similar to double-int except that it does not have the limitation that
math must be done on exactly two HOST_WIDE_INTs.

Internally, a wide_int is a structure that contains a fixed sized
array of HOST_WIDE_INTs, a length field and a mode.  The size of the
array is determined at generation time by dividing the number of bits
of the largest integer supported on the target by the number of bits
in a HOST_WIDE_INT of the host.  Thus, with this format, any length of
integer can be supported on any host.

A new rtx type is created, the CONST_WIDE_INT, which contains a
garbage collected array of HOST_WIDE_INTS that is large enough to hold
the constant.  For the targets that define TARGET_SUPPORTS_WIDE_INT to
be non zero, CONST_DOUBLES are only used to hold floating point
values.  If the target leaves TARGET_SUPPORTS_WIDE_INT defined as 0,
CONST_WIDE_INTs are not used and CONST_DOUBLEs are as they were
before.

CONST_INT does not change except that it is defined to hold all
constants that fit in exactly one HOST_WIDE_INT.  Note that is slightly
different than the current trunk.  Before this patch, the TImode
constant '5' could either be in a CONST_INT or CONST_DOUBLE depending
on which code path was used to create it.  This patch changes this so
that if the constant fits in a CONST_INT then it is represented in a
CONST_INT no matter how it is created.

For the array inside a CONST_WIDE_INT, and internally in wide-int, we
use a compressed form for integers that need more than one
HOST_WIDE_INT.  Higher elements of the array are not needed if they
are just a sign extension of the elements below them.  This does not
imply that constants are signed or are sign extended, this is only a
compression technique.

While it might seem to be more esthetically pleasing to have not
introduced the CONST_WIDE_INT and to have changed the representation
of the CONST_INT to accomodate larger numbers, this would have both
used more space and would be a time consuming change for the port
maintainers.  We believe that most ports can be quickly converted with
the current scheme because there is just not a lot of code in the back
ends that cares about large constants.  Furthermore, the CONST_INT is
very space efficient and even in a program that was heavy in large
values, most constants would still fit in a CONST_INT.

All of the parts of the rtl level that deal with CONST_DOUBLE as an
now conditionally work with CONST_WIDE_INTs depending on the value
of TARGET_SUPPORTS_WIDE_INT.  We believe that this patch removes all
of the ices and wrong code places at the portable rtl level. However,
there are still places in the portable rtl code that refuse to
transform the code unless it is a CONST_INT.  Since these do not cause
failures, they can be handled later.  The patch is already very large.

It should be noted that much of the constant overflow checking in the
constant math dissappears with these patches.  The overflow checking
code in the current compiler is really divided into two cases:
overflow on the host and overflow on the target.  The overflow
checking on the host was to make sure that the math did overflow when
done on two HOST_WIDE_INTs.  All of this code goes away.  These
patches allow the constant math to be done exactly the way it is done
on the target.

This patch also aids other cleanups that are being considered at the
rtl level:

   1) These patches remove most of the host dependencies on the
   optimizations.  Currently a 32 bit GCC host will produce different
   code for a specific target than a 64 bit host will.  This is because
   many of the transformations only work on constants that can be a
   represented with a single HWI or two HWIs.  If the target has larger
   integers than the host, the compilation suffers.

   2) Bernd's need to make GCC correctly support partial its is made
   easier by the wide-int library.  This library carefully does all
   arithmetic in the precision of the mode included in it.  While there
   are still places at the rtl level that still do arithmetic inline,
   we plan to convert those to use the library over time.   This patch
   converts a substantial number of those places.

   3) This patch is one step along the path to add modes to rtl integer
   constants.  There is no longer any checking to see if a CONST_DOUBLE
   has VOIDmode as its mode.  Furthermore, all constructors for various
   wide ints do take a mode and require that it not be VOIDmode. There
   is still a lot of work to do to make this conversion possible.

Richard Sandiford has been over the rtl portions of this patch a few
times.  He has not looked at the wide-int files in any detail.  This
patch has been heavily tested on my private ports and also on x86-64.


CONVERSION PROCESS

Converting a port mostly requires looking for the places where
CONST_DOUBLES are used with VOIDmode and replacing that code with code
that accesses CONST_WIDE_INTs.  "grep -i const_double" at the port
level gets you to 95% of the changes that need to be made.  There are
a few places that require a deeper look.

   1) There is no equivalent to hval and lval for CONST_WIDE_INTs.
   This would be difficult to express in the md language since there
   are a variable number of elements.

   Most ports only check that hval is either 0 or -1 to see if the int
   is small.  As mentioned above, this will no longer be necessary
   since small constants are always CONST_INT.  Of course there are
   still a few exceptions, the alpha's constraint used by the zap
   instruction certainly requires careful examination by C code.
   However, all the current code does is pass the hval and lval to C
   code, so evolving the c code to look at the CONST_WIDE_INT is not
   really a large change.

   2) Because there is no standard template that ports use to
   materialize constants, there is likely to be some futzing that is
   unique to each port in this code.

   3) The rtx costs may have to be adjusted to properly account for
   larger constants that are represented as CONST_WIDE_INT.

All and all it has not taken us long to convert ports that we are
familiar with.

OTHER COMMENTS

I did find what i believe is one interesting bug in the double-int
code.  I believe that the code that performs divide and mod with round
to nearest is seriously wrong for unsigned integers.  I believe that
it will get the wrong answer for any numbers that are large enough to
look negative if they consider signed integers.  Asside from that,
wide-int should perform in a very similar manner to double-int.

I am sorry for the size of this patch.   However, there does not appear
to change the underlying data structure to support wider integers
without doing something like this.

kenny
-------------- next part --------------
A non-text attachment was scrubbed...
Name: rtl3.diff
Type: text/x-patch
Size: 274911 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20121003/cf10895b/attachment.bin>
-------------- next part --------------
2012-10-3  Kenneth Zadeck <zadeck@naturalbridge.com>

	* reload.c (find_reloads): Use CONST_SCALAR_INT_P.
	rtl.def (CONST_WIDE_INT): New.
	* ira-costs.c (record_reg_classes, record_address_regs):
	Use CONST_SCALAR_INT_P.
	* dojump.c (prefer_and_bit_test): Use wide int api.
	* recog.c (simplify_while_replacing): Use CONST_SCALAR_INT_P.
 	(const_scalar_int_operand, const_double_operand): New versions
	if target supports wide integers.
	(const_wide_int_operand): New function.
	(asm_operand_ok, constrain_operands): Use CONST_SCALAR_INT_P.
	* rtl.c (DEF_RTL_EXPR): Added CONST_WIDE_INT case.
	(rtx_size): Ditto.
	(rtx_alloc_stat, hwivec_output_hex, hwivec_check_failed_bounds):
	New functions.
	(iterative_hash_rtx): Added CONST_WIDE_INT case.
	* rtl.h (hwivec_def): New function.
	(HWI_GET_NUM_ELEM, HWI_PUT_NUM_ELEM, CONST_WIDE_INT_P,
	CONST_SCALAR_INT_P, XHWIVEC_ELT, HWIVEC_CHECK, CONST_WIDE_INT_VEC,
	CONST_WIDE_INT_NUNITS, CONST_WIDE_INT_ELT, rtx_alloc_v): New macros.
	(chain_next): Added hwiv case.
	(CASE_CONST_SCALAR_INT, CONST_INT, CONST_WIDE_INT):  Added new
	defs if target supports wide ints.
	* rtlanal.c (commutative_operand_precedence): Added CONST_WIDE_INT
	case.
	* Makefile.in (wide-int.c, wide-int.h): New files.
	* sched-vis.c (print_value): Added CONST_WIDE_INT case are
	modified DOUBLE_INT case.
	* gengtype.c (wide-int): New type.
	* alias.c  (rtx_equal_for_memref_p): Fixed comment.
	* sel-sched-ir.c (lhs_and_rhs_separable_p): Ditto.
	* genemit.c (gen_exp): Added CONST_WIDE_INT case.
	* defaults.h (TARGET_SUPPORTS_WIDE_INT): New.
	* builtins.c (c_getstr, c_readstr, expand_builtin_signbit): 
	Make to work with any size int.
	* simplify-rtx.c (mode_signbit_p, simplify_unary_operation_1,
	simplify_const_unary_operation, simplify_binary_operation_1,
	simplify_const_binary_operation,
	simplify_relational_operation_1,
	simplify_const_relational_operation, simplify_immed_subreg,
	simplify_subreg): Ditto.
	* gengenrtl.c (excluded_rtx): Added CONST_WIDE_INT case.
	* expmed.c (mask_rtx, lshift_value): Now uses wide-int.
 	(expand_mult, expand_smod_pow2): Make to work with any size int.
	(make_tree): Added CONST_WIDE_INT case.
	* cselib.c (entry_and_rtx_equal_p): Use CONST_SCALAR_INT_P.
	(rtx_equal_for_cselib_1, cselib_hash_rtx): Added CONST_WIDE_INT case.
	* explow.c (plus_constant): Now uses wide-int api.
	* varasm.c (const_rtx_hash_1): Added CONST_WIDE_INT case.
	* hwint.c (popcount_hwi): New function.
	* hwint.h (HOST_BITS_PER_HALF_WIDE_INT, HOST_HALF_WIDE_INT,
	HOST_HALF_WIDE_INT_PRINT, HOST_HALF_WIDE_INT_PRINT_C,
	HOST_HALF_WIDE_INT_PRINT_DEC, HOST_HALF_WIDE_INT_PRINT_DEC_C,
	HOST_HALF_WIDE_INT_PRINT_UNSIGNED, HOST_HALF_WIDE_INT_PRINT_HEX,
	HOST_HALF_WIDE_INT_PRINT_HEX_PURE): New symbols.
	* postreload.c (reload_cse_simplify_set):  Now uses wide-int api.
	* var-tracking.c (loc_cmp): Added CONST_WIDE_INT case.
	* tree.c (wide_int_to_tree): New function.
	* tree.h (wide_int_to_tree): Ditto.
	* gensupport.c (const_wide_int_operand,
	const_scalar_int_operand): New
	* read-rtl.c (validate_const_wide_int): New function.
	(read_rtx_code): Added CONST_WIDE_INT case.
	* cse.c (hash_rtx_cb): Added CONST_WIDE_INT case are
	modified DOUBLE_INT case.
	* dwarf2out.c (dw_val_equal_p, size_of_loc_descr,
	output_loc_operands, print_die, attr_checksum, same_dw_val_p,
	size_of_die, value_format, output_die, mem_loc_descriptor,
	loc_descriptor, extract_int, add_const_value_attribute,
	hash_loc_operands, compare_loc_operands): Add support for wide-ints.
	(add_AT_wide): New function.
	* dwarf2out.h (enum dw_val_class): Added dw_val_class_wide_int.
	* wide-int.c (all): New file.
	* wide-int.h (all): New file.
	* genmodes.c (emit_max_int): New function.
	(emit_insn_modes_h): Add call to emit_max_int.
	* ira-lives.c (single_reg_class):  Use CONST_SCALAR_INT_P.
	* emit-rtl.c (const_wide_int_htab): Add marking.
	(const_wide_int_htab_hash, const_wide_int_htab_eq,
	lookup_const_wide_int, immed_wide_int_const): New functions.
	(const_double_htab_hash, const_double_htab_eq,
	rtx_to_double_int, immed_double_const): Conditionally 
	changed CONST_DOUBLE behavior.
 	(immed_double_const, init_emit_once): Changed to support wide-int.
	* combine.c (try_combine, subst, make_extraction, 
	gen_lowpart_for_combine): Changed to support any size integer.
	* print-rtl.c (print_rtx): Added CONST_WIDE_INT case.
	* genpreds.c (write_one_predicate_function): Fixed comment.
	(add_constraint): Added CONST_WIDE_INT test.
	(write_tm_constrs_h): Do not emit hval or lval if target
	supports wide integers.
	* tree-ssa-address.c (addr_for_mem_ref): Changes to use
	wide-int rather than double-int.
	* ggc-zone.c (ggc_alloc_typed_stat): Added
	gt_ggc_e_10hwivec_def case.
	* final.c (output_addr_const): Added CONST_WIDE_INT case.
	* coretypes.h (hwivec_def, hwivec, const_hwivec): New.
	* expr.c (convert_modes): Added support for any size int.
	(emit_group_load_1): Added todo for place that still does not
	allow large ints.
	(store_expr, expand_constructor): Fixed comments.
	(expand_expr_real_2, expand_expr_real_1,
	reduce_to_bit_field_precision, const_vector_from_tree):
	Converted to use wide-int api.
	* optabs.c (expand_subword_shift, expand_doubleword_shift,
	expand_absneg_bit, expand_absneg_bit, expand_copysign_absneg,
	expand_copysign_bit): Made to work with any size int.  
	* cfgexpand.c (expand_debug_locations):  Use CONST_SCALAR_INT_P.
	* ggc.h (ggc_alloc_hwivec_sized): New.