RFC: Representation of runtime offsets and sizes

The next main step in the SVE submission is to add support for
offsets and sizes that are a runtime invariant rather than a compile
time constant.  This is an RFC about our approach for doing that.
It's an update of https://gcc.gnu.org/ml/gcc/2016-11/msg00031.html
(which covered more topics than this message).

The size of an SVE register in bits can be any multiple of 128 between
128 and 2048 inclusive.  The way we chose to represent this was to
have a runtime indeterminate that counts the number of 128 bit blocks
above the minimum of 128.  If we call the indeterminate X then:

* an SVE register has 128 + 128 * X bits (16 + 16 * X bytes)
* the last int in an SVE vector is at byte offset 12 + 16 * X
* etc.

Although the maximum value of X is 15, we don't want to take advantage
of that, since there's nothing particularly magical about the value.

So we have two types of target: those for which there are no runtime
indeterminates, and those for which there is one runtime indeterminate.
We decided to generalise the interface slightly by allowing any number
of indeterminates, although the underlying implementation is still
limited to 0 and 1 for now.

The main class for working with these runtime offsets and sizes is
"poly_int".  It represents a value of the form:

  C0 + C1 * X1 + ... + Cn * Xn

where each coefficient Ci is a compile-time constant and where each
indeterminate Xi is a nonnegative runtime value.  The class takes two
template parameters, one giving the number of coefficients and one
giving the type of the coefficients.  There are then typedefs for the
common cases, with the number of coefficients being controlled by
the target.

poly_int is used for things like:

- the number of elements in a VECTOR_TYPE
- the size and number of units in a general machine_mode
- the offset of something in the stack frame
- SUBREG_BYTE
- MEM_SIZE and MEM_OFFSET
- mem_ref_offset

(only a selective list).  There are also rtx and tree representations
of poly_int, although I've left those out of this RFC.

The patch has detailed documentation -- which I've also attached as
a PDF -- but the main points are:

* there's no total ordering between poly_ints, so the best we can do
  when comparing them is to ask whether two values *might* or *must*
  be related in a particular way.  E.g. if mode A has size 2 + 2X
  and mode B has size 4, the condition:

    GET_MODE_SIZE (A) <= GET_MODE_SIZE (B)

  is true for X<=1 and false for X>=2.  This translates to:

    may_le (GET_MODE_SIZE (A), GET_MODE_SIZE (B)) == true
    must_le (GET_MODE_SIZE (A), GET_MODE_SIZE (B)) == false

  Of course, the may/must distinction already exists in things like
  alias analysis.

* some poly_int arithmetic operations (notably division) are only possible
  for certain values.  These operations therefore become conditional.

* target-independent code is exposed to these restrictions even if the
  current target has no indeterminates.  But:

  * we've tried to provide enough operations that poly_ints are easy
    to work with.

  * it means that developers working with non-SVE targets don't need
    to test SVE.  If the code compiles on a non-SVE target, and if it
    doesn't use any asserting operations, it's reasonable to assume
    that it will work on SVE too.

* for target-specific code, poly_int degenerates to a scalar if there
  are no runtime invariants for that target.  Only very minor changes
  are needed to non-AArch64 targets.

* poly_int operations should be (and in practice seem to be) as
  efficient as normal scalar operations on non-AArch64 targets.

The patch really needs some self-tests (which weren't supported when we
did the work originally), but otherwise it's what I'd like to submit.

Thanks,
Richard
10 Sizes and offsets as runtime invariants
******************************************

GCC allows the size of a hardware register to be a runtime invariant
rather than a compile-time constant.  This in turn means that various
sizes and offsets must also be runtime invariants rather than
compile-time constants, such as:

   * the size of a general 'machine_mode' (*note Machine Modes::);

   * the size of a spill slot;

   * the offset of something within a stack frame;

   * the number of elements in a vector;

   * the size and offset of a 'mem' rtx (*note Regs and Memory::); and

   * the byte offset in a 'subreg' rtx (*note Regs and Memory::).

 The motivating example is the Arm SVE ISA, whose vector registers can
be any multiple of 128 bits between 128 and 2048 inclusive.  The
compiler normally produces code that works for all SVE register sizes,
with the actual size only being known at runtime.

 GCC's main representation of such runtime invariants is the 'poly_int'
class.  This chapter describes what 'poly_int' does, lists the available
operations, and gives some general usage guidelines.

* Menu:

* Overview of poly_int::
* Consequences of using poly_int::
* Comparisons involving poly_int::
* Arithmetic on poly_ints::
* Alignment of poly_ints::
* Computing bounds on poly_ints::
* Converting poly_ints::
* Miscellaneous poly_int routines::
* Guidelines for using poly_int::

----
File: gccint.info,  Node: Overview of poly_int,  Next: Consequences of using poly_int,  Up: poly_int

10.1 Overview of 'poly_int'
===========================

We define indeterminates X1, ..., XN whose values are only known at
runtime and use polynomials of the form:

     C0 + C1 * X1 + ... + CN * XN

 to represent a size or offset whose value might depend on some of these
indeterminates.  The coefficients C0, ..., CN are always known at
compile time, with the C0 term being the "constant" part that does not
depend on any runtime value.

 GCC uses the 'poly_int' class to represent these coefficients.  The
class has two template parameters: the first specifies the number of
coefficients (N + 1) and the second specifies the type of the
coefficients.  For example, 'poly_int<2, unsigned short>' represents a
polynomial with two coefficients (and thus one indeterminate), with each
coefficient having type 'unsigned short'.  When N is 0, the class
degenerates to a single compile-time constant C0.

 The number of coefficients needed for compilation is a fixed property
of each target and is specified by the configuration macro
'NUM_POLY_INT_COEFFS'.  The default value is 1, since most targets do
not have such runtime invariants.  Targets that need a different value
should '#define' the macro in their 'CPU-modes.def' file.  *Note Back
End::.

 'poly_int' makes the simplifying requirement that each indeterminate
must be a nonnegative integer.  An indeterminate value of 0 should
usually represent the minimum possible runtime value, with C0 specifying
the value in that case.

 For example, when targetting the Arm SVE ISA, the single indeterminate
represents the number of 128-bit blocks in a vector _beyond the minimum
length of 128 bits_.  Thus the number of 64-bit doublewords in a vector
is 2 + 2 * X1.  If an aggregate has a single SVE vector and 16
additional bytes, its total size is 32 + 16 * X1 bytes.

 The header file 'poly-int-types.h' provides typedefs for the most
common forms of 'poly_int', all having 'NUM_POLY_INT_COEFFS'
coefficients:

'poly_uint16'
     a 'poly_int' with 'unsigned short' coefficients.

'poly_int64'
     a 'poly_int' with 'HOST_WIDE_INT' coefficients.

'poly_uint64'
     a 'poly_int' with 'unsigned HOST_WIDE_INT' coefficients.

'poly_offset_int'
     a 'poly_int' with 'offset_int' coefficients.

'poly_wide_int'
     a 'poly_int' with 'wide_int' coefficients.

'poly_widest_int'
     a 'poly_int' with 'widest_int' coefficients.

 Since the main purpose of 'poly_int' is to represent sizes and offsets,
the last two typedefs are only rarely used.

----
File: gccint.info,  Node: Consequences of using poly_int,  Next: Comparisons involving poly_int,  Prev: Overview of poly_int,  Up: poly_int

10.2 Consequences of using 'poly_int'
=====================================

The two main consequences of using polynomial sizes and offsets are
that:

   * there is no total ordering between the values at compile time, and

   * some operations might yield results that cannot be expressed as a
     'poly_int'.

 For example, if X is a runtime invariant, we cannot tell at compile
time whether:

     3 + 4X <= 1 + 5X

 since the condition is false when X <= 1 and true when X >= 2.

 Similarly, 'poly_int' cannot represent the result of:

     (3 + 4X) * (1 + 5X)

 since it cannot (and in practice does not need to) store powers greater
than one.  It also cannot represent the result of:

     (3 + 4X) / (1 + 5X)

 The following sections describe how we deal with these restrictions.

 As described earlier, a 'poly_int<1, T>' has no indeterminates and so
degenerates to a compile-constant of type T.  It would be possible in
that case to do all normal arithmetic on the T, and to compare the T
using the normal C++ operators.  We deliberately prevent
target-independent code from doing this, since the compiler needs to
support other 'poly_int<N, T>' as well, regardless of the current
target's 'NUM_POLY_INT_COEFFS'.

 However, it would be very artificial to force target-specific code to
follow these restrictions if the target has no runtime indeterminates.
There is therefore an implicit conversion from 'poly_int<1, T>' to T
when compiling target-specific translation units.

----
File: gccint.info,  Node: Comparisons involving poly_int,  Next: Arithmetic on poly_ints,  Prev: Consequences of using poly_int,  Up: poly_int

10.3 Comparisons involving 'poly_int'
=====================================

In general we need to compare sizes and offsets in two situations: those
in which the values need to be ordered, and those in which the values
can be unordered.  More loosely, the distinction is often between values
that have a definite link (usually because they refer to the same
underlying register or memory location) and values that have no definite
link.  An example of the former is the relationship between the inner
and outer sizes of a subreg, where we must know at compile time whether
the subreg is paradoxical, partial, or complete.  An example of the
latter is alias analysis: we might want to check whether two arbitrary
memory references overlap.

 Referring back to the examples in the previous section, it makes sense
to ask whether a memory reference of size '3 + 4X' overlaps one of size
'1 + 5X', but it does not make sense to have a subreg in which the outer
mode has '3 + 4X' bytes and the inner mode has '1 + 5X' bytes (or vice
versa).  Such subregs are always invalid and should trigger an internal
compiler error if formed.

 The underlying operators are the same in both cases, but the
distinction affects how they are used.

* Menu:

* Comparison functions for poly_int::
* Properties of the poly_int comparisons::
* Comparing potentially-unordered poly_ints::
* Comparing ordered poly_ints::
* Checking for a poly_int marker value::
* Range checks on poly_ints::
* Sorting poly_ints::

----
File: gccint.info,  Node: Comparison functions for poly_int,  Next: Properties of the poly_int comparisons,  Up: Comparisons involving poly_int

10.3.1 Comparison functions for 'poly_int'
------------------------------------------

'poly_int' provides the following routines for checking whether a
particular relationship "may" (might) hold:

     may_lt may_le may_eq may_ge may_gt
                   may_ne

 The functions have their natural meaning:

'may_lt(A, B)'
     Return true if A might be less than B.

'may_le(A, B)'
     Return true if A might be less than or equal to B.

'may_eq(A, B)'
     Return true if A might be equal to B.

'may_ne(A, B)'
     Return true if A might not be equal to B.

'may_ge(A, B)'
     Return true if A might be greater than or equal to B.

'may_gt(A, B)'
     Return true if A might be greater than B.

 For readability, 'poly_int' also provides "must" inverses of these
functions:

     must_lt (A, B) == !may_ge (A, B)
     must_le (A, B) == !may_gt (A, B)
     must_eq (A, B) == !may_ne (A, B)
     must_ge (A, B) == !may_lt (A, B)
     must_gt (A, B) == !may_le (A, B)
     must_ne (A, B) == !may_eq (A, B)

----
File: gccint.info,  Node: Properties of the poly_int comparisons,  Next: Comparing potentially-unordered poly_ints,  Prev: Comparison functions for poly_int,  Up: Comparisons involving poly_int

10.3.2 Properties of the 'poly_int' comparisons
-----------------------------------------------

All "may" relations except 'may_ne' are transitive, so for example:

     may_lt (A, B) && may_lt (B, C) implies may_lt (A, C)

 for all A, B and C.  'may_lt', 'may_gt' and 'may_ne' are irreflexive,
so for example:

     !may_lt (A, A)

 is true for all A.  'may_le', 'may_eq' and 'may_ge' are reflexive, so
for example:

     may_le (A, A)

 is true for all A.  'may_eq' and 'may_ne' are symmetric, so:

     may_eq (A, B) == may_eq (B, A)
     may_ne (A, B) == may_ne (B, A)

 for all A and B.  In addition:

     may_le (A, B) == may_lt (A, B) || may_eq (A, B)
     may_ge (A, B) == may_gt (A, B) || may_eq (A, B)
     may_lt (A, B) == may_gt (B, A)
     may_le (A, B) == may_ge (B, A)

 However:

     may_le (A, B) && may_le (B, A) does not imply !may_ne (A, B) [== must_eq(A, B)]
     may_ge (A, B) && may_ge (B, A) does not imply !may_ne (A, B) [== must_eq(A, B)]

 One example is again 'A == 3 + 4X' and 'B == 1 + 5X', where 'may_le (A,
B)', 'may_ge (A, B)' and 'may_ne (A, B)' all hold.  'may_le' and
'may_ge' are therefore not antisymetric and do not form a partial order.

 From the above, it follows that:

   * All "must" relations except 'must_ne' are transitive.

   * 'must_lt', 'must_ne' and 'must_gt' are irreflexive.

   * 'must_le', 'must_eq' and 'must_ge' are reflexive.

 Also:

     must_lt (A, B) == must_gt (B, A)
     must_le (A, B) == must_ge (B, A)
     must_lt (A, B) implies !must_lt (B, A)  [asymmetry]
     must_gt (A, B) implies !must_gt (B, A)
     must_le (A, B) && must_le (B, A) == must_eq (A, B) [== !may_ne (A, B)]
     must_ge (A, B) && must_ge (B, A) == must_eq (A, B) [== !may_ne (A, B)]

 'must_le' and 'must_ge' are therefore antisymmetric and are partial
orders.  However:

     must_le (A, B) does not imply must_lt (A, B) || must_eq (A, B)
     must_ge (A, B) does not imply must_gt (A, B) || must_eq (A, B)

 For example, 'must_le (4, 4 + 4X)' holds because the runtime
indeterminate X is a nonnegative integer, but neither 'must_lt (4, 4 +
4X)' nor 'must_eq (4, 4 + 4X)' hold.

----
File: gccint.info,  Node: Comparing potentially-unordered poly_ints,  Next: Comparing ordered poly_ints,  Prev: Properties of the poly_int comparisons,  Up: Comparisons involving poly_int

10.3.3 Comparing potentially-unordered 'poly_int's
--------------------------------------------------

In cases where there is no definite link between two 'poly_int's, we can
usually make a conservatively-correct assumption.  For example, the
conservative assumption for alias analysis is that two references
_might_ alias.

 One way of checking whether [BEGIN1, END1) might overlap [BEGIN2, END2)
using the 'poly_int' comparisons is:

     may_gt (END1, BEGIN2) && may_gt (END2, BEGIN1)

 and another is:

     !(must_le (END1, BEGIN2) || must_le (END2, BEGIN1))

 However, in this particular example, it is better to use the range
helper functions instead.  *Note Range checks on poly_ints::.

----
File: gccint.info,  Node: Comparing ordered poly_ints,  Next: Checking for a poly_int marker value,  Prev: Comparing potentially-unordered poly_ints,  Up: Comparisons involving poly_int

10.3.4 Comparing ordered 'poly_int's
------------------------------------

In cases where there is a definite link between two 'poly_int's, such as
the outer and inner sizes of subregs, we usually require the sizes to be
ordered by the 'must_le' partial order.  'poly_int' provides the
following utility functions for ordered values:

'ordered_p (A, B)'
     Return true if A and B are ordered by the 'must_le' partial order.

'ordered_min (A, B)'
     Assert that A and B are ordered by 'must_le' and return the minimum
     of the two.  When using this function, please add a comment
     explaining why the values are known to be ordered.

'ordered_max (A, B)'
     Assert that A and B are ordered by 'must_le' and return the maximum
     of the two.  When using this function, please add a comment
     explaining why the values are known to be ordered.

 For example, if a subreg has an outer mode of size OUTER and an inner
mode of size INNER:

   * the subreg is complete if must_eq (INNER, OUTER)

   * otherwise, the subreg is paradoxical if must_le (INNER, OUTER)

   * otherwise, the subreg is partial if must_le (OUTER, INNER)

   * otherwise, the subreg is ill-formed

 Thus the subreg is only valid if 'ordered_p (OUTER, INNER)' is true.
If this condition is already known to be true then:

   * the subreg is complete if must_eq (INNER, OUTER)

   * the subreg is paradoxical if may_lt (INNER, OUTER)

   * the subreg is partial if may_lt (OUTER, INNER)

 with the three conditions being mutually-exclusive.

 Code that checks whether a subreg is valid would therefore generally
check whether 'ordered_p' holds (in addition to whatever other checks
are required for subreg validity).  Code that is dealing with existing
subregs can assert that 'ordered_p' holds and use either of the
classifications above.

----
File: gccint.info,  Node: Checking for a poly_int marker value,  Next: Range checks on poly_ints,  Prev: Comparing ordered poly_ints,  Up: Comparisons involving poly_int

10.3.5 Checking for a 'poly_int' marker value
---------------------------------------------

It is sometimes useful to have a special "marker value" that is not
meant to be taken literally.  For example, some code uses a size of -1
to represent an unknown size, rather than having to carry around a
separate boolean to say whether the size is known.

 The best way of checking whether something is a marker value is
'must_eq'.  Conversely the best way of checking whether something is
_not_ a marker value is 'may_ne'.

 Thus in the size example just mentioned, 'must_eq (size, -1)' would
check for an unknown size and 'may_ne (size, -1)' would check for a
known size.

----
File: gccint.info,  Node: Range checks on poly_ints,  Next: Sorting poly_ints,  Prev: Checking for a poly_int marker value,  Up: Comparisons involving poly_int

10.3.6 Range checks on 'poly_int's
----------------------------------

As well as the core comparisons (*note Comparison functions for
poly_int::), 'poly_int' provides utilities for various kinds of range
check.  In each case the range is represented by a start position and a
length rather than a start position and an end position; this is because
the former is used much more often than the latter in GCC.  Also, the
sizes can be -1 (or all ones for unsigned sizes) to indicate a range
with a known start position but an unknown size.

'ranges_may_overlap_p (POS1, SIZE1, POS2, SIZE2)'
     Return true if the range described by POS1 and SIZE1 _might_
     overlap the range described by POS2 and SIZE2.

'ranges_must_overlap_p (POS1, SIZE1, POS2, SIZE2)'
     Return true if the range described by POS1 and SIZE1 is known to
     overlap the range described by POS2 and SIZE2.

'known_subrange_p (POS1, SIZE1, POS2, SIZE2)'
     Return true if the range described by POS1 and SIZE1 is known to be
     contained in the range described by POS2 and SIZE2.

'maybe_in_range_p (VALUE, POS, SIZE)'
     Return true if VALUE _might_ be in the range described by POS and
     SIZE (in other words, return true if VALUE is not known to be
     outside that range).

'known_in_range_p (VALUE, POS, SIZE)'
     Return true if VALUE is known to be in the range described by POS
     and SIZE.

----
File: gccint.info,  Node: Sorting poly_ints,  Prev: Range checks on poly_ints,  Up: Comparisons involving poly_int

10.3.7 Sorting 'poly_int's
--------------------------

'poly_int' provides the following routine for sorting:

'compare_sizes_for_sort (A, B)'
     Compare A and B in reverse lexicographical order (that is, compare
     the highest-indexed coefficients first).  This can be useful when
     sorting data structures, since it has the effect of separating
     constant and non-constant values.  If all values are nonnegative,
     the constant values come first.

     Note that the values do not necessarily end up in numerical order.
     For example, '1 + 1X' would come after '100' in the sort order, but
     may well be less than '100' at run time.

----
File: gccint.info,  Node: Arithmetic on poly_ints,  Next: Alignment of poly_ints,  Prev: Comparisons involving poly_int,  Up: poly_int

10.4 Arithmetic on 'poly_int's
==============================

Addition, subtraction, negation and bit inversion all work normally for
'poly_int's.  Multiplication by a constant multiplier and left shifting
by a constant shift amount also work normally.  General multiplication
of two 'poly_int's is not supported and is not useful in practice.

 Other operations are only conditionally supported: the operation might
succeed or might fail, depending on the inputs.

 This section describes both types of operation.

* Menu:

* Using poly_int with C++ arithmetic operators::
* wi arithmetic on poly_ints::
* Division of poly_ints::
* Other poly_int arithmetic::

----
File: gccint.info,  Node: Using poly_int with C++ arithmetic operators,  Next: wi arithmetic on poly_ints,  Up: Arithmetic on poly_ints

10.4.1 Using 'poly_int' with C++ arithmetic operators
-----------------------------------------------------

The following C++ expressions are supported, where P1 and P2 are
'poly_int's and where C1 and C2 are scalars:

     -P1
     ~P1

     P1 + P2
     P1 + C2
     C1 + P2

     P1 - P2
     P1 - C2
     C1 - P2

     C1 * P2
     P1 * C2

     P1 << C2

     P1 += P2
     P1 += C2

     P1 -= P2
     P1 -= C2

     P1 *= C2
     P1 <<= C2

 These arithmetic operations handle integer ranks in a similar way to
C++.  The main difference is that every coefficient narrower than
'HOST_WIDE_INT' promotes to 'HOST_WIDE_INT', whereas in C++ everything
narrower than 'int' promotes to 'int'.  For example:

     poly_uint16     + int          -> poly_int64
     unsigned int    + poly_uint16  -> poly_int64
     poly_int64      + int          -> poly_int64
     poly_int32      + poly_uint64  -> poly_uint64
     uint64          + poly_int64   -> poly_uint64
     poly_offset_int + int32        -> poly_offset_int
     offset_int      + poly_uint16  -> poly_offset_int

 In the first two examples, both coefficients are narrower than
'HOST_WIDE_INT', so the result has coefficients of type 'HOST_WIDE_INT'.
In the other examples, the coefficient with the highest rank "wins".

 If one of the operands is 'wide_int' or 'poly_wide_int', the rules are
the same as for 'wide_int' arithmetic.

----
File: gccint.info,  Node: wi arithmetic on poly_ints,  Next: Division of poly_ints,  Prev: Using poly_int with C++ arithmetic operators,  Up: Arithmetic on poly_ints

10.4.2 'wi' arithmetic on 'poly_int's
-------------------------------------

As well as the C++ operators, 'poly_int' supports the following
overflow-checking 'wi' routines:

     wi::neg (P1, &OVERFLOW)

     wi::add (P1, P2, SIGN, &OVERFLOW)
     wi::sub (P1, P2, SIGN, &OVERFLOW)
     wi::mul (P1, C2, SIGN, &OVERFLOW)

 These routines just check whether overflow occurs on any individual
coefficient; it is not possible to know at compile time whether the
final runtime value would overflow.

----
File: gccint.info,  Node: Division of poly_ints,  Next: Other poly_int arithmetic,  Prev: wi arithmetic on poly_ints,  Up: Arithmetic on poly_ints

10.4.3 Division of 'poly_int's
------------------------------

Division of 'poly_int's is possible for certain inputs.  The functions
for division return true if the operation is possible and in most cases
return the results by pointer.  The routines are:

'multiple_p (A, B)'
'multiple_p (A, B, &QUOTIENT)'
     Return true if A is an exact multiple of B, storing the result in
     QUOTIENT if so.  There are overloads for various combinations of
     polynomial and constant A, B and QUOTIENT.

'constant_multiple_p (A, B)'
'constant_multiple_p (A, B, &QUOTIENT)'
     Like 'multiple_p', but also test whether the multiple is a
     compile-time constant.

'can_div_trunc_p (A, B, &QUOTIENT)'
'can_div_trunc_p (A, B, &QUOTIENT, &REMAINDER)'
     Return true if we can calculate 'trunc (A / B)' at compile time,
     storing the result in QUOTIENT and REMAINDER if so.

'can_div_away_from_zero_p (A, B, &QUOTIENT)'
     Return true if we can calculate 'A / B' at compile time, rounding
     away from zero.  Store the result in QUOTIENT if so.

     Note that this is true if and only if 'can_div_trunc_p' is true.
     The only difference is in the rounding of the result.

 There is also an asserting form of division:

'exact_div (A, B)'
     Assert that A is a multiple of B and return 'A / B'.  The result is
     a 'poly_int' if A is a 'poly_int'.

----
File: gccint.info,  Node: Other poly_int arithmetic,  Prev: Division of poly_ints,  Up: Arithmetic on poly_ints

10.4.4 Other 'poly_int' arithmetic
----------------------------------

There are tentative routines for other operations besides division:

'can_ior_p (A, B, &RESULT)'
     Return true if we can calculate 'A | B' at compile time, storing
     the result in RESULT if so.

 Also, ANDs with a value '(1 << Y) - 1' or its inverse can be treated as
alignment operations.  *Note Alignment of poly_ints::.

 In addition, the following miscellaneous routines are available:

'coeff_gcd (A)'
     Return the greatest common divisor of all nonzero coefficients in
     A, or zero if A is known to be zero.

'common_multiple (A, B)'
     Return a value that is a multiple of both A and B, where one value
     is a 'poly_int' and the other is a scalar.  The result will be the
     least common multiple for some indeterminate values but not
     necessarily for all.

'force_common_multiple (A, B)'
     Return a value that is a multiple of both A and B, asserting that
     such a value exists.  The result will be the least common multiple
     for some indeterminate values but not necessarily for all.

     When using this routine, please add a comment explaining why the
     assertion is known to hold.

 Please add any other operations that you find to be useful.

----
File: gccint.info,  Node: Alignment of poly_ints,  Next: Computing bounds on poly_ints,  Prev: Arithmetic on poly_ints,  Up: poly_int

10.5 Alignment of 'poly_int's
=============================

'poly_int' provides various routines for aligning values and for
querying misalignments.  In each case the alignment must be a power of
2.

'can_align_p (VALUE, ALIGN)'
     Return true if we can align VALUE up or down to the nearest
     multiple of ALIGN at compile time.  The answer is the same for both
     directions.

'can_align_down (VALUE, ALIGN, &ALIGNED)'
     Return true if 'can_align_p'; if so, set ALIGNED to the greatest
     aligned value that is less than or equal to VALUE.

'can_align_up (VALUE, ALIGN, &ALIGNED)'
     Return true if 'can_align_p'; if so, set ALIGNED to the lowest
     aligned value that is greater than or equal to VALUE.

'known_equal_after_align_down (A, B, ALIGN)'
     Return true if we can align A and B down to the nearest ALIGN
     boundary at compile time and if the two results are equal.

'known_equal_after_align_up (A, B, ALIGN)'
     Return true if we can align A and B up to the nearest ALIGN
     boundary at compile time and if the two results are equal.

'aligned_lower_bound (VALUE, ALIGN)'
     Return a result that is no greater than VALUE and that is aligned
     to ALIGN.  The result will the closest aligned value for some
     indeterminate values but not necessarily for all.

     For example, suppose we are allocating an object of SIZE bytes in a
     downward-growing stack whose current limit is given by LIMIT.  If
     the object requires ALIGN bytes of alignment, the new stack limit
     is given by:

          aligned_lower_bound (LIMIT - SIZE, ALIGN)

'aligned_upper_bound (VALUE, ALIGN)'
     Likewise return a result that is no less than VALUE and that is
     aligned to ALIGN.  This is the routine that would be used for
     upward-growing stacks in the scenario just described.

'known_misalignment (VALUE, ALIGN, &MISALIGN)'
     Return true if we can calculate the misalignment of VALUE with
     respect to ALIGN at compile time, storing the result in MISALIGN if
     so.

'known_alignment (VALUE)'
     Return the minimum alignment that VALUE is known to have (in other
     words, the largest alignment that can be guaranteed whatever the
     values of the indeterminates turn out to be).  Return 0 if VALUE is
     known to be 0.

'force_align_down (VALUE, ALIGN)'
     Assert that VALUE can be aligned down to ALIGN at compile time and
     return the result.  When using this routine, please add a comment
     explaining why the assertion is known to hold.

'force_align_up (VALUE, ALIGN)'
     Likewise, but aligning up.

'force_align_down_and_div (VALUE, ALIGN)'
     Divide the result of 'force_align_down' by ALIGN.  Again, please
     add a comment explaining why the assertion in 'force_align_down' is
     known to hold.

'force_align_up_and_div (VALUE, ALIGN)'
     Likewise for 'force_align_up'.

'force_get_misalignment (VALUE, ALIGN)'
     Assert that we can calculate the misalignment of VALUE with respect
     to ALIGN at compile time and return the misalignment.  When using
     this function, please add a comment explaining why the assertion is
     known to hold.

----
File: gccint.info,  Node: Computing bounds on poly_ints,  Next: Converting poly_ints,  Prev: Alignment of poly_ints,  Up: poly_int

10.6 Computing bounds on 'poly_int's
====================================

'poly_int' also provides routines for calculating lower and upper
bounds:

'constant_lower_bound (A)'
     Assert that A is nonnegative and return the smallest value it can
     have.

'lower_bound (A, B)'
     Return a value that is always less than or equal to both A and B.
     It will be the greatest such value for some indeterminate values
     but necessarily for all.

'upper_bound (A, B)'
     Return a value that is always greater than or equal to both A and
     B.  It will be the least such value for some indeterminate values
     but necessarily for all.

----
File: gccint.info,  Node: Converting poly_ints,  Next: Miscellaneous poly_int routines,  Prev: Computing bounds on poly_ints,  Up: poly_int

10.7 Converting 'poly_int's
===========================

A 'poly_int<N, T>' can be constructed from up to N individual T
coefficients, with the remaining coefficients being implicitly zero.  In
particular, this means that every 'poly_int<N, T>' can be constructed
from a single scalar T, or someting compatible with T.

 Also, a 'poly_int<N, T>' can be constructed from a 'poly_int<N, U>' if
T can be constructed from U.

 The following functions provide other forms of conversion, or test
whether such a conversion would succeed.

'VALUE.is_constant ()'
     Return true if 'poly_int' VALUE is a compile-time constant.

'VALUE.is_constant (&C1)'
     Return true if 'poly_int' VALUE is a compile-time constant, storing
     it in C1 if so.  C1 must be able to hold all constant values of
     VALUE without loss of precision.

'VALUE.to_constant ()'
     Assert that VALUE is a compile-time constant and return its value.
     When using this function, please add a comment explaining why the
     condition is known to hold (for example, because an earlier phase
     of analysis rejected non-constants).

'VALUE.to_shwi (&P2)'
     Return true if 'poly_int<N, T>' VALUE can be represented without
     loss of precision as a 'poly_int<N, 'HOST_WIDE_INT'>', storing it
     in that form in P2 if so.

'VALUE.to_uhwi (&P2)'
     Return true if 'poly_int<N, T>' VALUE can be represented without
     loss of precision as a 'poly_int<N, 'unsigned HOST_WIDE_INT'>',
     storing it in that form in P2 if so.

'VALUE.force_shwi ()'
     Forcibly convert each coefficient of 'poly_int<N, T>' VALUE to
     'HOST_WIDE_INT', truncating any that are out of range.  Return the
     result as a 'poly_int<N, 'HOST_WIDE_INT'>'.

'VALUE.force_uhwi ()'
     Forcibly convert each coefficient of 'poly_int<N, T>' VALUE to
     'unsigned HOST_WIDE_INT', truncating any that are out of range.
     Return the result as a 'poly_int<N, 'unsigned HOST_WIDE_INT'>'.

'wi::sext (VALUE, PRECISION)'
     Return a 'poly_int' of the same type as VALUE, sign-extending every
     coefficient from the low PRECISION bits.  This in effect applies
     'wi::sext' to each coefficient individually.

'poly_wide_int::from (VALUE, PRECISION, SIGN)'
     Convert VALUE to a 'poly_wide_int' in which each coefficient has
     PRECISION bits.  Extend the coefficients according to SIGN if the
     coefficients have fewer bits.

'poly_offset_int::from (VALUE, SIGN)'
     Convert VALUE to a 'poly_offset_int', extending its coefficients
     according to SIGN if they have fewer bits than 'offset_int'.

'poly_widest_int::from (VALUE, SIGN)'
     Convert VALUE to a 'poly_widest_int', extending its coefficients
     according to SIGN if they have fewer bits than 'widest_int'.

----
File: gccint.info,  Node: Miscellaneous poly_int routines,  Next: Guidelines for using poly_int,  Prev: Converting poly_ints,  Up: poly_int

10.8 Miscellaneous 'poly_int' routines
======================================

'print_dec (VALUE, FILE, SIGN)'
     Print VALUE to FILE as a decimal value, interpreting the
     coefficients according to SIGN.  This is a simply a 'poly_int'
     version of a wide-int routine.

----
File: gccint.info,  Node: Guidelines for using poly_int,  Prev: Miscellaneous poly_int routines,  Up: poly_int

10.9 Guidelines for using 'poly_int'
====================================

One of the main design goals of 'poly_int' was to make it easy to write
target-independent code that handles variable-sized registers even when
the current target has fixed-sized registers.  There are two aspects to
this:

   * The set of 'poly_int' operations should be complete enough that the
     question in most cases becomes "Can we do this operation on these
     particular 'poly_int' values?  If not, bail out" rather than "Are
     these 'poly_int' values constant?  If so, do the operation,
     otherwise bail out".

   * If target-independent code compiles and runs correctly on a target
     with one value of 'NUM_POLY_INT_COEFFS', and if the code does not
     use asserting functions like 'to_constant', it is reasonable to
     assume that the code also works on targets with other values of
     'NUM_POLY_INT_COEFFS'.  There is no need to check this during
     everyday development.

 So the general principle is: if target-independent code is dealing with
a 'poly_int' value, it is better to operate on it as a 'poly_int' if at
all possible, choosing conservatively-correct behavior if a particular
operation fails.  For example, the following code handles an index 'pos'
into a sequence of vectors that each have 'nunits' elements:

     /* Calculate which vector contains the result, and which lane of
        that vector we need.  */
     if (!can_div_trunc_p (pos, nunits, &vec_entry, &vec_index))
       {
         if (dump_enabled_p ())
           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
                            "Cannot determine which vector holds the"
                            " final result.\n");
         return false;
       }

 However, there are some contexts in which operating on a 'poly_int' is
not possible or does not make sense.  One example is when handling
static initializers, since no current target supports the concept of a
variable-length static initializer.  In these situations, a reasonable
fallback is:

     if (POLY_VALUE.is_constant (&CONST_VALUE))
       {
         ...
         /* Operate on CONST_VALUE.  */
         ...
       }
     else
       {
         ...
         /* Conservatively correct fallback.  */
         ...
       }

 'poly_int' also provides some asserting functions like 'to_constant'.
Please only use these functions if there is a good theoretical reason to
believe that the assertion cannot fire.  For example if some work is
divided into an analysis phase and an implementation phase, the analysis
phase might reject inputs that are not 'is_constant', in which case the
implementation phase can reasonably use 'to_constant' on the remaining
inputs.  The assertions should not be used to discover whether a
condition ever occurs "in the field"; in other words, they should not be
used to restrict code to constants at first, with the intention of only
implementing a 'poly_int' version if a user hits the assertion.

 If a particular asserting function like 'to_constant' is needed more
than once for the same reason, it is probably worth adding a helper
function or macro for that situation, so that the justification only
needs to be given once.  For example:

     /* Return the size of an element in a vector of size SIZE, given that
        the vector has NELTS elements.  The return value is in the same units
        as SIZE (either bits or bytes).

        to_constant () is safe in this situation because vector elements are
        always constant-sized scalars.  */
     #define vector_element_size(SIZE, NELTS) \
       (exact_div (SIZE, NELTS).to_constant ())

 Target-specific code in 'config/CPU' only needs to handle non-constant
'poly_int's if 'NUM_POLY_INT_COEFFS' is greater than one.  For other
targets, 'poly_int' degenerates to a compile-time constant and is often
interchangable with a normal salar integer.  There are two main
exceptions:

   * Sometimes an explicit cast to an integer type might be needed, such
     as to resolve ambiguities in a '?:' expression, or when passing
     values through '...' to things like print functions.

   * Target macros are included in target-independent code and so do not
     have access to the implicit conversion to a scalar integer.  If
     this becomes a problem for a particular target macro, the possible
     solutions, in order of preference, are:

        * Convert the target macro to a target hook (for all targets).

        * Put the target's implementation of the target macro in its
          'CPU.c' file and call it from the target macro in the 'CPU.h'
          file.

        * Add 'to_constant ()' calls where necessary.  The previous
          option is preferable because it will help with any future
          conversion of the macro to a hook.
2017-09-06  Richard Sandiford  <richard.sandiford@linaro.org>
	    Alan Hayward  <alan.hayward@arm.com>
	    David Sherwood  <david.sherwood@arm.com>

gcc/
	* poly-int.h: New file.
	* poly-int-types.h: Likewise.
	* coretypes.h: Include them.
	(POLY_INT_CONVERSION): Define.
	* target.def (estimated_poly_value): New hook.
	* doc/tm.texi.in (TARGET_ESTIMATED_POLY_VALUE): New hook.
	* doc/tm.texi: Regenerate.
	* doc/poly-int.texi: New file.
	* doc/gccint.texi: Include it.
	* Makefile.in (TEXI_GCCINT_FILES): Add poly-int.texi.
	* genmodes.c (NUM_POLY_INT_COEFFS): Provide default definition.
	(emit_insn_modes_h): Emit a definition of NUM_POLY_INT_COEFFS.
	* targhooks.h (default_estimated_poly_value): Declare.
	* targhooks.c (default_estimated_poly_value): New function.
	* target.h (estimated_poly_value): Likewise.
	* wide-int.h (WI_UNARY_RESULT): Use wi::binary_traits.
	(wi::unary_traits): Delete.
	(operator /): New function.
	(operator %): Likewise.

Message ID	87mv678ttb.fsf@linaro.org
State	New
Headers	show Delivered-To: patch@linaro.org Received: by 10.140.94.166 with SMTP id g35csp1461712qge; Wed, 6 Sep 2017 13:19:45 -0700 (PDT) X-Received: by 10.84.211.12 with SMTP id b12mr347709pli.365.1504729185805; Wed, 06 Sep 2017 13:19:45 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1504729185; cv=none; d=google.com; s=arc-20160816; b=oit7YCxboK6ZNLbUqKfTAYoluaJ6KEkVOHRxMXNwh8C2mJ1jVDmR4tpIDs0cfERnNT yTTbpWxLLf12b9AGBaLP1uGKjk3RIgvDTZWLbVSUV2dRpJ+ioUoolKGc1iW+rMivtF3s zyx5Z+1tXWc3QD0U9tmrQMPDTWzZ7OmcU99hiAp1Vca2fjf2nFQa+MGzg3km+PytKsWV 67MMg6mo7V0H/DhADd78BF4151sfSfXPZ8OimDmlal2KuMO1D/JCZsWj3gUBYy0ZLcUq Alf74n1QyaecklWt0lQ32ixB5A7/X2R/5jllS0NcC7XzfO5NJysFoIIl7PufsFjzrI3B th/w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=mime-version:user-agent:message-id:date:subject:mail-followup-to:to :from:delivered-to:sender:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=/AR/qPf7uMmLNiMuRs1VyUXb009pY69LLem2fnRT/JM=; b=Ck6/xBSwZMelgPqd/gVu85OgZfzMoi57erjmNjA0+h9gVlrxqw5ROmX06gfn9PBRNi M2QmyZ+PUdBFuuWwsuKLab1C/Pyk8RWd7xc6Z0X2QUxEGtLfdQ2B4I/TVnSbAL3kSTcf NmIrgkpPPwXyyJn5pwGk/m1TTfegYT2AhOnHejd6LUDk33qqRI4+wBTuz3otW8NwcD/S uxwXqh2j4NUM+Aj5rw7+BXCUy8G9EJqHs2F3lgXgSLVAvkwgU2JtPOGp+mqtHRW8VKpg 7rRL0E28ktW5hj2X647xQRuQnB42sKHFlrZRATSH8m5g2ipMqFyqDcsKfWfUQMp8FQfJ 1EYQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=RHgtq9BK; spf=pass (google.com: domain of gcc-patches-return-461644-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-461644-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: <gcc-patches-return-461644-patch=linaro.org@gcc.gnu.org> Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id 33si480415plo.315.2017.09.06.13.19.42 for <patch@linaro.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 06 Sep 2017 13:19:45 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-461644-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=RHgtq9BK; spf=pass (google.com: domain of gcc-patches-return-461644-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-461644-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; q=dns; s= default; b=WuNZ+WDgs/ymwfU50SiuP0mcuZ+pdqlDaowiZdLcggTWG9ralk9jW 97WgepDVoOv6708Ol5P+tG46119yX5NpaR8ynNBsYABAnamwdcR1Te01y7paQ4LR 1TNRD90+xn+ll0KUseVq5zOpqFFdefjyg5SZgtWxkiRq811azdvYjs= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; s= default; bh=tdyzrnNfWCcEU6kAzKAv7NUBb00=; b=RHgtq9BKwPw/JfmYLwqP d1rGyyX7Hyk460GcOo0pDmeB+g1KIn298Dr9yYZYjM7zkSS2CL9F+W+yzaKoOyK1 YhnuZLDMZ1fjvpBk3hAH2fKzek/zb+Aw8Hq3gL2jcsGGIol4X2GN8OGnZVoxTyWW cXhUZZ65GTEXWgrRr014ZXg= Received: (qmail 70785 invoked by alias); 6 Sep 2017 20:19:00 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: <gcc-patches.gcc.gnu.org> List-Unsubscribe: <mailto:gcc-patches-unsubscribe-patch=linaro.org@gcc.gnu.org> List-Archive: <http://gcc.gnu.org/ml/gcc-patches/> List-Post: <mailto:gcc-patches@gcc.gnu.org> List-Help: <mailto:gcc-patches-help@gcc.gnu.org> Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 69811 invoked by uid 89); 6 Sep 2017 20:19:00 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-15.4 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-wr0-f170.google.com Received: from mail-wr0-f170.google.com (HELO mail-wr0-f170.google.com) (209.85.128.170) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 06 Sep 2017 20:18:38 +0000 Received: by mail-wr0-f170.google.com with SMTP id o42so5288718wrb.3 for <gcc-patches@gcc.gnu.org>; Wed, 06 Sep 2017 13:18:37 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:mail-followup-to:subject:date:message-id :user-agent:mime-version; bh=W2klzBaLkozJRGnK7UA7BgO9pkr3yNjmmn56QNW63zU=; b=ozNx6RUZOXD5vcCHufWWEoYPL3t4WVPwzUtpSImtI48No0b8v472QhlhkfZ2ZiKPpt HxJ+849PUX1Cc9336j4YdiF25yLcdYw/JdeSvdBP/U63Eyvpif6Bp3oTAlaCQk4AfHyq 6uT79Hq3CFq6FOK38N+TBEQY+Ghd+S72X25WHf9Lbpa+omBze5K7Js2kt1Du3k+kCQ65 utFI2VWY8Hlnr+gtrM/jpQFNGYRDhfheqpvEgwNwfiA15Yr8oYXxrOarq5P2t/mCIY3Q sFOURzmMkOBiSasdjLLs3U5f/SlCEspMHw2wfCphHNeSZw9dTv7BVW1yeixiRE3TtCQ8 DEiw== X-Gm-Message-State: AHPjjUi55GONQxL2TU5ZALwEYhtOjXbiEJ3qa6SU5FF9VmA6GB9vjoAA Ox3G4EJo5xShYqaZyO3DNg== X-Google-Smtp-Source: ADKCNb7aFFYOCR/qJUXX00VSVLTYxLa3/fvHUnsnWDkNRKFSpIgQ9GDVsC6S5rNcSYjd6OZXueYQKQ== X-Received: by 10.223.152.199 with SMTP id w65mr240695wrb.254.1504729115291; Wed, 06 Sep 2017 13:18:35 -0700 (PDT) Received: from localhost ([95.145.139.63]) by smtp.gmail.com with ESMTPSA id e80sm1645651wmd.45.2017.09.06.13.18.26 for <gcc-patches@gcc.gnu.org> (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 06 Sep 2017 13:18:33 -0700 (PDT) From: Richard Sandiford <richard.sandiford@linaro.org> To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@linaro.org Subject: RFC: Representation of runtime offsets and sizes Date: Wed, 06 Sep 2017 21:18:24 +0100 Message-ID: <87mv678ttb.fsf@linaro.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux) MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-="
Series	RFC: Representation of runtime offsets and sizes \| expand RFC: Representation of runtime offsets and sizes

RFC: Representation of runtime offsets and sizes

Commit Message

Comments

Patch