@node poly_int | |

@chapter Sizes and offsets as runtime invariants | |

@cindex polynomial integers | |

@findex poly_int | |

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: | |

@itemize @bullet | |

@item | |

the size of a general @code{machine_mode} (@pxref{Machine Modes}); | |

@item | |

the size of a spill slot; | |

@item | |

the offset of something within a stack frame; | |

@item | |

the number of elements in a vector; | |

@item | |

the size and offset of a @code{mem} rtx (@pxref{Regs and Memory}); and | |

@item | |

the byte offset in a @code{subreg} rtx (@pxref{Regs and Memory}). | |

@end itemize | |

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 | |

@code{poly_int} class. This chapter describes what @code{poly_int} | |

does, lists the available operations, and gives some general | |

usage guidelines. | |

@menu | |

* Overview of @code{poly_int}:: | |

* Consequences of using @code{poly_int}:: | |

* Comparisons involving @code{poly_int}:: | |

* Arithmetic on @code{poly_int}s:: | |

* Alignment of @code{poly_int}s:: | |

* Computing bounds on @code{poly_int}s:: | |

* Converting @code{poly_int}s:: | |

* Miscellaneous @code{poly_int} routines:: | |

* Guidelines for using @code{poly_int}:: | |

@end menu | |

@node Overview of @code{poly_int} | |

@section Overview of @code{poly_int} | |

@cindex @code{poly_int}, runtime value | |

We define indeterminates @var{x1}, @dots{}, @var{xn} whose values are | |

only known at runtime and use polynomials of the form: | |

@smallexample | |

@var{c0} + @var{c1} * @var{x1} + @dots{} + @var{cn} * @var{xn} | |

@end smallexample | |

to represent a size or offset whose value might depend on some | |

of these indeterminates. The coefficients @var{c0}, @dots{}, @var{cn} | |

are always known at compile time, with the @var{c0} term being the | |

``constant'' part that does not depend on any runtime value. | |

GCC uses the @code{poly_int} class to represent these coefficients. | |

The class has two template parameters: the first specifies the number of | |

coefficients (@var{n} + 1) and the second specifies the type of the | |

coefficients. For example, @samp{poly_int<2, unsigned short>} represents | |

a polynomial with two coefficients (and thus one indeterminate), with each | |

coefficient having type @code{unsigned short}. When @var{n} is 0, | |

the class degenerates to a single compile-time constant @var{c0}. | |

@cindex @code{poly_int}, template parameters | |

@findex NUM_POLY_INT_COEFFS | |

The number of coefficients needed for compilation is a fixed | |

property of each target and is specified by the configuration macro | |

@code{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 @code{#define} the macro in their @file{@var{cpu}-modes.def} | |

file. @xref{Back End}. | |

@cindex @code{poly_int}, invariant range | |

@code{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 @var{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 @emph{beyond the minimum | |

length of 128 bits}. Thus the number of 64-bit doublewords in a vector | |

is 2 + 2 * @var{x1}. If an aggregate has a single SVE vector and 16 | |

additional bytes, its total size is 32 + 16 * @var{x1} bytes. | |

The header file @file{poly-int-types.h} provides typedefs for the | |

most common forms of @code{poly_int}, all having | |

@code{NUM_POLY_INT_COEFFS} coefficients: | |

@cindex @code{poly_int}, main typedefs | |

@table @code | |

@item poly_uint16 | |

a @samp{poly_int} with @code{unsigned short} coefficients. | |

@item poly_int64 | |

a @samp{poly_int} with @code{HOST_WIDE_INT} coefficients. | |

@item poly_uint64 | |

a @samp{poly_int} with @code{unsigned HOST_WIDE_INT} coefficients. | |

@item poly_offset_int | |

a @samp{poly_int} with @code{offset_int} coefficients. | |

@item poly_wide_int | |

a @samp{poly_int} with @code{wide_int} coefficients. | |

@item poly_widest_int | |

a @samp{poly_int} with @code{widest_int} coefficients. | |

@end table | |

Since the main purpose of @code{poly_int} is to represent sizes and | |

offsets, the last two typedefs are only rarely used. | |

@node Consequences of using @code{poly_int} | |

@section Consequences of using @code{poly_int} | |

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

@itemize | |

@item | |

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

@item | |

some operations might yield results that cannot be expressed as a | |

@code{poly_int}. | |

@end itemize | |

For example, if @var{x} is a runtime invariant, we cannot tell at | |

compile time whether: | |

@smallexample | |

3 + 4@var{x} <= 1 + 5@var{x} | |

@end smallexample | |

since the condition is false when @var{x} <= 1 and true when @var{x} >= 2. | |

Similarly, @code{poly_int} cannot represent the result of: | |

@smallexample | |

(3 + 4@var{x}) * (1 + 5@var{x}) | |

@end smallexample | |

since it cannot (and in practice does not need to) store powers greater | |

than one. It also cannot represent the result of: | |

@smallexample | |

(3 + 4@var{x}) / (1 + 5@var{x}) | |

@end smallexample | |

The following sections describe how we deal with these restrictions. | |

@cindex @code{poly_int}, use in target-independent code | |

As described earlier, a @code{poly_int<1, @var{T}>} has no indeterminates | |

and so degenerates to a compile-time constant of type @var{T}. It would | |

be possible in that case to do all normal arithmetic on the @var{T}, | |

and to compare the @var{T} using the normal C++ operators. We deliberately | |

prevent target-independent code from doing this, since the compiler needs | |

to support other @code{poly_int<@var{n}, @var{T}>} as well, regardless of | |

the current target's @code{NUM_POLY_INT_COEFFS}. | |

@cindex @code{poly_int}, use in target-specific code | |

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 @code{poly_int<1, @var{T}>} | |

to @var{T} when compiling target-specific translation units. | |

@node Comparisons involving @code{poly_int} | |

@section Comparisons involving @code{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 @samp{3 + 4@var{x}} overlaps | |

one of size @samp{1 + 5@var{x}}, but it does not make sense to have a | |

subreg in which the outer mode has @samp{3 + 4@var{x}} bytes and the | |

inner mode has @samp{1 + 5@var{x}} 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 @code{poly_int}:: | |

* Properties of the @code{poly_int} comparisons:: | |

* Comparing potentially-unordered @code{poly_int}s:: | |

* Comparing ordered @code{poly_int}s:: | |

* Checking for a @code{poly_int} marker value:: | |

* Range checks on @code{poly_int}s:: | |

* Sorting @code{poly_int}s:: | |

@end menu | |

@node Comparison functions for @code{poly_int} | |

@subsection Comparison functions for @code{poly_int} | |

@code{poly_int} provides the following routines for checking whether | |

a particular condition ``may be'' (might be) true: | |

@example | |

maybe_lt maybe_le maybe_eq maybe_ge maybe_gt | |

maybe_ne | |

@end example | |

The functions have their natural meaning: | |

@table @samp | |

@item maybe_lt(@var{a}, @var{b}) | |

Return true if @var{a} might be less than @var{b}. | |

@item maybe_le(@var{a}, @var{b}) | |

Return true if @var{a} might be less than or equal to @var{b}. | |

@item maybe_eq(@var{a}, @var{b}) | |

Return true if @var{a} might be equal to @var{b}. | |

@item maybe_ne(@var{a}, @var{b}) | |

Return true if @var{a} might not be equal to @var{b}. | |

@item maybe_ge(@var{a}, @var{b}) | |

Return true if @var{a} might be greater than or equal to @var{b}. | |

@item maybe_gt(@var{a}, @var{b}) | |

Return true if @var{a} might be greater than @var{b}. | |

@end table | |

For readability, @code{poly_int} also provides ``known'' inverses of these | |

functions: | |

@example | |

known_lt (@var{a}, @var{b}) == !maybe_ge (@var{a}, @var{b}) | |

known_le (@var{a}, @var{b}) == !maybe_gt (@var{a}, @var{b}) | |

known_eq (@var{a}, @var{b}) == !maybe_ne (@var{a}, @var{b}) | |

known_ge (@var{a}, @var{b}) == !maybe_lt (@var{a}, @var{b}) | |

known_gt (@var{a}, @var{b}) == !maybe_le (@var{a}, @var{b}) | |

known_ne (@var{a}, @var{b}) == !maybe_eq (@var{a}, @var{b}) | |

@end example | |

@node Properties of the @code{poly_int} comparisons | |

@subsection Properties of the @code{poly_int} comparisons | |

All ``maybe'' relations except @code{maybe_ne} are transitive, so for example: | |

@smallexample | |

maybe_lt (@var{a}, @var{b}) && maybe_lt (@var{b}, @var{c}) implies maybe_lt (@var{a}, @var{c}) | |

@end smallexample | |

for all @var{a}, @var{b} and @var{c}. @code{maybe_lt}, @code{maybe_gt} | |

and @code{maybe_ne} are irreflexive, so for example: | |

@smallexample | |

!maybe_lt (@var{a}, @var{a}) | |

@end smallexample | |

is true for all @var{a}. @code{maybe_le}, @code{maybe_eq} and @code{maybe_ge} | |

are reflexive, so for example: | |

@smallexample | |

maybe_le (@var{a}, @var{a}) | |

@end smallexample | |

is true for all @var{a}. @code{maybe_eq} and @code{maybe_ne} are symmetric, so: | |

@smallexample | |

maybe_eq (@var{a}, @var{b}) == maybe_eq (@var{b}, @var{a}) | |

maybe_ne (@var{a}, @var{b}) == maybe_ne (@var{b}, @var{a}) | |

@end smallexample | |

for all @var{a} and @var{b}. In addition: | |

@smallexample | |

maybe_le (@var{a}, @var{b}) == maybe_lt (@var{a}, @var{b}) || maybe_eq (@var{a}, @var{b}) | |

maybe_ge (@var{a}, @var{b}) == maybe_gt (@var{a}, @var{b}) || maybe_eq (@var{a}, @var{b}) | |

maybe_lt (@var{a}, @var{b}) == maybe_gt (@var{b}, @var{a}) | |

maybe_le (@var{a}, @var{b}) == maybe_ge (@var{b}, @var{a}) | |

@end smallexample | |

However: | |

@smallexample | |

maybe_le (@var{a}, @var{b}) && maybe_le (@var{b}, @var{a}) does not imply !maybe_ne (@var{a}, @var{b}) [== known_eq (@var{a}, @var{b})] | |

maybe_ge (@var{a}, @var{b}) && maybe_ge (@var{b}, @var{a}) does not imply !maybe_ne (@var{a}, @var{b}) [== known_eq (@var{a}, @var{b})] | |

@end smallexample | |

One example is again @samp{@var{a} == 3 + 4@var{x}} | |

and @samp{@var{b} == 1 + 5@var{x}}, where @samp{maybe_le (@var{a}, @var{b})}, | |

@samp{maybe_ge (@var{a}, @var{b})} and @samp{maybe_ne (@var{a}, @var{b})} | |

all hold. @code{maybe_le} and @code{maybe_ge} are therefore not antisymetric | |

and do not form a partial order. | |

From the above, it follows that: | |

@itemize @bullet | |

@item | |

All ``known'' relations except @code{known_ne} are transitive. | |

@item | |

@code{known_lt}, @code{known_ne} and @code{known_gt} are irreflexive. | |

@item | |

@code{known_le}, @code{known_eq} and @code{known_ge} are reflexive. | |

@end itemize | |

Also: | |

@smallexample | |

known_lt (@var{a}, @var{b}) == known_gt (@var{b}, @var{a}) | |

known_le (@var{a}, @var{b}) == known_ge (@var{b}, @var{a}) | |

known_lt (@var{a}, @var{b}) implies !known_lt (@var{b}, @var{a}) [asymmetry] | |

known_gt (@var{a}, @var{b}) implies !known_gt (@var{b}, @var{a}) | |

known_le (@var{a}, @var{b}) && known_le (@var{b}, @var{a}) == known_eq (@var{a}, @var{b}) [== !maybe_ne (@var{a}, @var{b})] | |

known_ge (@var{a}, @var{b}) && known_ge (@var{b}, @var{a}) == known_eq (@var{a}, @var{b}) [== !maybe_ne (@var{a}, @var{b})] | |

@end smallexample | |

@code{known_le} and @code{known_ge} are therefore antisymmetric and are | |

partial orders. However: | |

@smallexample | |

known_le (@var{a}, @var{b}) does not imply known_lt (@var{a}, @var{b}) || known_eq (@var{a}, @var{b}) | |

known_ge (@var{a}, @var{b}) does not imply known_gt (@var{a}, @var{b}) || known_eq (@var{a}, @var{b}) | |

@end smallexample | |

For example, @samp{known_le (4, 4 + 4@var{x})} holds because the runtime | |

indeterminate @var{x} is a nonnegative integer, but neither | |

@code{known_lt (4, 4 + 4@var{x})} nor @code{known_eq (4, 4 + 4@var{x})} hold. | |

@node Comparing potentially-unordered @code{poly_int}s | |

@subsection Comparing potentially-unordered @code{poly_int}s | |

In cases where there is no definite link between two @code{poly_int}s, | |

we can usually make a conservatively-correct assumption. For example, | |

the conservative assumption for alias analysis is that two references | |

@emph{might} alias. | |

One way of checking whether [@var{begin1}, @var{end1}) might overlap | |

[@var{begin2}, @var{end2}) using the @code{poly_int} comparisons is: | |

@smallexample | |

maybe_gt (@var{end1}, @var{begin2}) && maybe_gt (@var{end2}, @var{begin1}) | |

@end smallexample | |

and another (equivalent) way is: | |

@smallexample | |

!(known_le (@var{end1}, @var{begin2}) || known_le (@var{end2}, @var{begin1})) | |

@end smallexample | |

However, in this particular example, it is better to use the range helper | |

functions instead. @xref{Range checks on @code{poly_int}s}. | |

@node Comparing ordered @code{poly_int}s | |

@subsection Comparing ordered @code{poly_int}s | |

In cases where there is a definite link between two @code{poly_int}s, | |

such as the outer and inner sizes of subregs, we usually require the sizes | |

to be ordered by the @code{known_le} partial order. @code{poly_int} provides | |

the following utility functions for ordered values: | |

@table @samp | |

@item ordered_p (@var{a}, @var{b}) | |

Return true if @var{a} and @var{b} are ordered by the @code{known_le} | |

partial order. | |

@item ordered_min (@var{a}, @var{b}) | |

Assert that @var{a} and @var{b} are ordered by @code{known_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. | |

@item ordered_max (@var{a}, @var{b}) | |

Assert that @var{a} and @var{b} are ordered by @code{known_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. | |

@end table | |

For example, if a subreg has an outer mode of size @var{outer} and an | |

inner mode of size @var{inner}: | |

@itemize @bullet | |

@item | |

the subreg is complete if known_eq (@var{inner}, @var{outer}) | |

@item | |

otherwise, the subreg is paradoxical if known_le (@var{inner}, @var{outer}) | |

@item | |

otherwise, the subreg is partial if known_le (@var{outer}, @var{inner}) | |

@item | |

otherwise, the subreg is ill-formed | |

@end itemize | |

Thus the subreg is only valid if | |

@samp{ordered_p (@var{outer}, @var{inner})} is true. If this condition | |

is already known to be true then: | |

@itemize @bullet | |

@item | |

the subreg is complete if known_eq (@var{inner}, @var{outer}) | |

@item | |

the subreg is paradoxical if maybe_lt (@var{inner}, @var{outer}) | |

@item | |

the subreg is partial if maybe_lt (@var{outer}, @var{inner}) | |

@end itemize | |

with the three conditions being mutually exclusive. | |

Code that checks whether a subreg is valid would therefore generally | |

check whether @code{ordered_p} holds (in addition to whatever other | |

checks are required for subreg validity). Code that is dealing | |

with existing subregs can assert that @code{ordered_p} holds | |

and use either of the classifications above. | |

@node Checking for a @code{poly_int} marker value | |

@subsection Checking for a @code{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 | |

@code{known_eq}. Conversely the best way of checking whether something | |

is @emph{not} a marker value is @code{maybe_ne}. | |

Thus in the size example just mentioned, @samp{known_eq (size, -1)} would | |

check for an unknown size and @samp{maybe_ne (size, -1)} would check for a | |

known size. | |

@node Range checks on @code{poly_int}s | |

@subsection Range checks on @code{poly_int}s | |

As well as the core comparisons | |

(@pxref{Comparison functions for @code{poly_int}}), @code{poly_int} provides | |

utilities for various kinds of range check. In each case the range | |

is represented by a start position and a size 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. All other sizes must be nonnegative. | |

A range of size 0 does not contain anything or overlap anything. | |

@table @samp | |

@item known_size_p (@var{size}) | |

Return true if @var{size} represents a known range size, false if it | |

is -1 or all ones (for signed and unsigned types respectively). | |

@item ranges_maybe_overlap_p (@var{pos1}, @var{size1}, @var{pos2}, @var{size2}) | |

Return true if the range described by @var{pos1} and @var{size1} @emph{might} | |

overlap the range described by @var{pos2} and @var{size2} (in other words, | |

return true if we cannot prove that the ranges are disjoint). | |

@item ranges_known_overlap_p (@var{pos1}, @var{size1}, @var{pos2}, @var{size2}) | |

Return true if the range described by @var{pos1} and @var{size1} is known to | |

overlap the range described by @var{pos2} and @var{size2}. | |

@item known_subrange_p (@var{pos1}, @var{size1}, @var{pos2}, @var{size2}) | |

Return true if the range described by @var{pos1} and @var{size1} is known to | |

be contained in the range described by @var{pos2} and @var{size2}. | |

@item maybe_in_range_p (@var{value}, @var{pos}, @var{size}) | |

Return true if @var{value} @emph{might} be in the range described by | |

@var{pos} and @var{size} (in other words, return true if we cannot | |

prove that @var{value} is outside that range). | |

@item known_in_range_p (@var{value}, @var{pos}, @var{size}) | |

Return true if @var{value} is known to be in the range described | |

by @var{pos} and @var{size}. | |

@item endpoint_representable_p (@var{pos}, @var{size}) | |

Return true if the range described by @var{pos} and @var{size} is | |

open-ended or if the endpoint (@var{pos} + @var{size}) is representable | |

in the same type as @var{pos} and @var{size}. The function returns false | |

if adding @var{size} to @var{pos} makes conceptual sense but could overflow. | |

@end table | |

There is also a @code{poly_int} version of the @code{IN_RANGE_P} macro: | |

@table @samp | |

@item coeffs_in_range_p (@var{x}, @var{lower}, @var{upper}) | |

Return true if every coefficient of @var{x} is in the inclusive range | |

[@var{lower}, @var{upper}]. This function can be useful when testing | |

whether an operation would cause the values of coefficients to | |

overflow. | |

Note that the function does not indicate whether @var{x} itself is in the | |

given range. @var{x} can be either a constant or a @code{poly_int}. | |

@end table | |

@node Sorting @code{poly_int}s | |

@subsection Sorting @code{poly_int}s | |

@code{poly_int} provides the following routine for sorting: | |

@table @samp | |

@item compare_sizes_for_sort (@var{a}, @var{b}) | |

Compare @var{a} and @var{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, @samp{1 + 1@var{x}} would come after @samp{100} in the sort order, | |

but may well be less than @samp{100} at run time. | |

@end table | |

@node Arithmetic on @code{poly_int}s | |

@section Arithmetic on @code{poly_int}s | |

Addition, subtraction, negation and bit inversion all work normally for | |

@code{poly_int}s. Multiplication by a constant multiplier and left | |

shifting by a constant shift amount also work normally. General | |

multiplication of two @code{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 @code{poly_int} with C++ arithmetic operators:: | |

* @code{wi} arithmetic on @code{poly_int}s:: | |

* Division of @code{poly_int}s:: | |

* Other @code{poly_int} arithmetic:: | |

@end menu | |

@node Using @code{poly_int} with C++ arithmetic operators | |

@subsection Using @code{poly_int} with C++ arithmetic operators | |

The following C++ expressions are supported, where @var{p1} and @var{p2} | |

are @code{poly_int}s and where @var{c1} and @var{c2} are scalars: | |

@smallexample | |

-@var{p1} | |

~@var{p1} | |

@var{p1} + @var{p2} | |

@var{p1} + @var{c2} | |

@var{c1} + @var{p2} | |

@var{p1} - @var{p2} | |

@var{p1} - @var{c2} | |

@var{c1} - @var{p2} | |

@var{c1} * @var{p2} | |

@var{p1} * @var{c2} | |

@var{p1} << @var{c2} | |

@var{p1} += @var{p2} | |

@var{p1} += @var{c2} | |

@var{p1} -= @var{p2} | |

@var{p1} -= @var{c2} | |

@var{p1} *= @var{c2} | |

@var{p1} <<= @var{c2} | |

@end smallexample | |

These arithmetic operations handle integer ranks in a similar way | |

to C++. The main difference is that every coefficient narrower than | |

@code{HOST_WIDE_INT} promotes to @code{HOST_WIDE_INT}, whereas in | |

C++ everything narrower than @code{int} promotes to @code{int}. | |

For example: | |

@smallexample | |

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 | |

@end smallexample | |

In the first two examples, both coefficients are narrower than | |

@code{HOST_WIDE_INT}, so the result has coefficients of type | |

@code{HOST_WIDE_INT}. In the other examples, the coefficient | |

with the highest rank ``wins''. | |

If one of the operands is @code{wide_int} or @code{poly_wide_int}, | |

the rules are the same as for @code{wide_int} arithmetic. | |

@node @code{wi} arithmetic on @code{poly_int}s | |

@subsection @code{wi} arithmetic on @code{poly_int}s | |

As well as the C++ operators, @code{poly_int} supports the following | |

@code{wi} routines: | |

@smallexample | |

wi::neg (@var{p1}, &@var{overflow}) | |

wi::add (@var{p1}, @var{p2}) | |

wi::add (@var{p1}, @var{c2}) | |

wi::add (@var{c1}, @var{p1}) | |

wi::add (@var{p1}, @var{p2}, @var{sign}, &@var{overflow}) | |

wi::sub (@var{p1}, @var{p2}) | |

wi::sub (@var{p1}, @var{c2}) | |

wi::sub (@var{c1}, @var{p1}) | |

wi::sub (@var{p1}, @var{p2}, @var{sign}, &@var{overflow}) | |

wi::mul (@var{p1}, @var{c2}) | |

wi::mul (@var{c1}, @var{p1}) | |

wi::mul (@var{p1}, @var{c2}, @var{sign}, &@var{overflow}) | |

wi::lshift (@var{p1}, @var{c2}) | |

@end smallexample | |

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. | |

@node Division of @code{poly_int}s | |

@subsection Division of @code{poly_int}s | |

Division of @code{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: | |

@table @samp | |

@item multiple_p (@var{a}, @var{b}) | |

@itemx multiple_p (@var{a}, @var{b}, &@var{quotient}) | |

Return true if @var{a} is an exact multiple of @var{b}, storing the result | |

in @var{quotient} if so. There are overloads for various combinations | |

of polynomial and constant @var{a}, @var{b} and @var{quotient}. | |

@item constant_multiple_p (@var{a}, @var{b}) | |

@itemx constant_multiple_p (@var{a}, @var{b}, &@var{quotient}) | |

Like @code{multiple_p}, but also test whether the multiple is a | |

compile-time constant. | |

@item can_div_trunc_p (@var{a}, @var{b}, &@var{quotient}) | |

@itemx can_div_trunc_p (@var{a}, @var{b}, &@var{quotient}, &@var{remainder}) | |

Return true if we can calculate @samp{trunc (@var{a} / @var{b})} at compile | |

time, storing the result in @var{quotient} and @var{remainder} if so. | |

@item can_div_away_from_zero_p (@var{a}, @var{b}, &@var{quotient}) | |

Return true if we can calculate @samp{@var{a} / @var{b}} at compile time, | |

rounding away from zero. Store the result in @var{quotient} if so. | |

Note that this is true if and only if @code{can_div_trunc_p} is true. | |

The only difference is in the rounding of the result. | |

@end table | |

There is also an asserting form of division: | |

@table @samp | |

@item exact_div (@var{a}, @var{b}) | |

Assert that @var{a} is a multiple of @var{b} and return | |

@samp{@var{a} / @var{b}}. The result is a @code{poly_int} if @var{a} | |

is a @code{poly_int}. | |

@end table | |

@node Other @code{poly_int} arithmetic | |

@subsection Other @code{poly_int} arithmetic | |

There are tentative routines for other operations besides division: | |

@table @samp | |

@item can_ior_p (@var{a}, @var{b}, &@var{result}) | |

Return true if we can calculate @samp{@var{a} | @var{b}} at compile time, | |

storing the result in @var{result} if so. | |

@end table | |

Also, ANDs with a value @samp{(1 << @var{y}) - 1} or its inverse can be | |

treated as alignment operations. @xref{Alignment of @code{poly_int}s}. | |

In addition, the following miscellaneous routines are available: | |

@table @samp | |

@item coeff_gcd (@var{a}) | |

Return the greatest common divisor of all nonzero coefficients in | |

@var{a}, or zero if @var{a} is known to be zero. | |

@item common_multiple (@var{a}, @var{b}) | |

Return a value that is a multiple of both @var{a} and @var{b}, where | |

one value is a @code{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. | |

@item force_common_multiple (@var{a}, @var{b}) | |

Return a value that is a multiple of both @code{poly_int} @var{a} and | |

@code{poly_int} @var{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. | |

@end table | |

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

@node Alignment of @code{poly_int}s | |

@section Alignment of @code{poly_int}s | |

@code{poly_int} provides various routines for aligning values and for querying | |

misalignments. In each case the alignment must be a power of 2. | |

@table @samp | |

@item can_align_p (@var{value}, @var{align}) | |

Return true if we can align @var{value} up or down to the nearest multiple | |

of @var{align} at compile time. The answer is the same for both directions. | |

@item can_align_down (@var{value}, @var{align}, &@var{aligned}) | |

Return true if @code{can_align_p}; if so, set @var{aligned} to the greatest | |

aligned value that is less than or equal to @var{value}. | |

@item can_align_up (@var{value}, @var{align}, &@var{aligned}) | |

Return true if @code{can_align_p}; if so, set @var{aligned} to the lowest | |

aligned value that is greater than or equal to @var{value}. | |

@item known_equal_after_align_down (@var{a}, @var{b}, @var{align}) | |

Return true if we can align @var{a} and @var{b} down to the nearest | |

@var{align} boundary at compile time and if the two results are equal. | |

@item known_equal_after_align_up (@var{a}, @var{b}, @var{align}) | |

Return true if we can align @var{a} and @var{b} up to the nearest | |

@var{align} boundary at compile time and if the two results are equal. | |

@item aligned_lower_bound (@var{value}, @var{align}) | |

Return a result that is no greater than @var{value} and that is aligned | |

to @var{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 @var{size} bytes | |

in a downward-growing stack whose current limit is given by @var{limit}. | |

If the object requires @var{align} bytes of alignment, the new stack | |

limit is given by: | |

@smallexample | |

aligned_lower_bound (@var{limit} - @var{size}, @var{align}) | |

@end smallexample | |

@item aligned_upper_bound (@var{value}, @var{align}) | |

Likewise return a result that is no less than @var{value} and that is | |

aligned to @var{align}. This is the routine that would be used for | |

upward-growing stacks in the scenario just described. | |

@item known_misalignment (@var{value}, @var{align}, &@var{misalign}) | |

Return true if we can calculate the misalignment of @var{value} | |

with respect to @var{align} at compile time, storing the result in | |

@var{misalign} if so. | |

@item known_alignment (@var{value}) | |

Return the minimum alignment that @var{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 @var{value} is known to be 0. | |

@item force_align_down (@var{value}, @var{align}) | |

Assert that @var{value} can be aligned down to @var{align} at compile | |

time and return the result. When using this routine, please add a | |

comment explaining why the assertion is known to hold. | |

@item force_align_up (@var{value}, @var{align}) | |

Likewise, but aligning up. | |

@item force_align_down_and_div (@var{value}, @var{align}) | |

Divide the result of @code{force_align_down} by @var{align}. Again, | |

please add a comment explaining why the assertion in @code{force_align_down} | |

is known to hold. | |

@item force_align_up_and_div (@var{value}, @var{align}) | |

Likewise for @code{force_align_up}. | |

@item force_get_misalignment (@var{value}, @var{align}) | |

Assert that we can calculate the misalignment of @var{value} with | |

respect to @var{align} at compile time and return the misalignment. | |

When using this function, please add a comment explaining why | |

the assertion is known to hold. | |

@end table | |

@node Computing bounds on @code{poly_int}s | |

@section Computing bounds on @code{poly_int}s | |

@code{poly_int} also provides routines for calculating lower and upper bounds: | |

@table @samp | |

@item constant_lower_bound (@var{a}) | |

Assert that @var{a} is nonnegative and return the smallest value it can have. | |

@item constant_lower_bound_with_limit (@var{a}, @var{b}) | |

Return the least value @var{a} can have, given that the context in | |

which @var{a} appears guarantees that the answer is no less than @var{b}. | |

In other words, the caller is asserting that @var{a} is greater than or | |

equal to @var{b} even if @samp{known_ge (@var{a}, @var{b})} doesn't hold. | |

@item constant_upper_bound_with_limit (@var{a}, @var{b}) | |

Return the greatest value @var{a} can have, given that the context in | |

which @var{a} appears guarantees that the answer is no greater than @var{b}. | |

In other words, the caller is asserting that @var{a} is less than or equal | |

to @var{b} even if @samp{known_le (@var{a}, @var{b})} doesn't hold. | |

@item lower_bound (@var{a}, @var{b}) | |

Return a value that is always less than or equal to both @var{a} and @var{b}. | |

It will be the greatest such value for some indeterminate values | |

but necessarily for all. | |

@item upper_bound (@var{a}, @var{b}) | |

Return a value that is always greater than or equal to both @var{a} and | |

@var{b}. It will be the least such value for some indeterminate values | |

but necessarily for all. | |

@end table | |

@node Converting @code{poly_int}s | |

@section Converting @code{poly_int}s | |

A @code{poly_int<@var{n}, @var{T}>} can be constructed from up to | |

@var{n} individual @var{T} coefficients, with the remaining coefficients | |

being implicitly zero. In particular, this means that every | |

@code{poly_int<@var{n}, @var{T}>} can be constructed from a single | |

scalar @var{T}, or something compatible with @var{T}. | |

Also, a @code{poly_int<@var{n}, @var{T}>} can be constructed from | |

a @code{poly_int<@var{n}, @var{U}>} if @var{T} can be constructed | |

from @var{U}. | |

The following functions provide other forms of conversion, | |

or test whether such a conversion would succeed. | |

@table @samp | |

@item @var{value}.is_constant () | |

Return true if @code{poly_int} @var{value} is a compile-time constant. | |

@item @var{value}.is_constant (&@var{c1}) | |

Return true if @code{poly_int} @var{value} is a compile-time constant, | |

storing it in @var{c1} if so. @var{c1} must be able to hold all | |

constant values of @var{value} without loss of precision. | |

@item @var{value}.to_constant () | |

Assert that @var{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). | |

@item @var{value}.to_shwi (&@var{p2}) | |

Return true if @samp{poly_int<@var{N}, @var{T}>} @var{value} can be | |

represented without loss of precision as a | |

@samp{poly_int<@var{N}, @code{HOST_WIDE_INT}>}, storing it in that | |

form in @var{p2} if so. | |

@item @var{value}.to_uhwi (&@var{p2}) | |

Return true if @samp{poly_int<@var{N}, @var{T}>} @var{value} can be | |

represented without loss of precision as a | |

@samp{poly_int<@var{N}, @code{unsigned HOST_WIDE_INT}>}, storing it in that | |

form in @var{p2} if so. | |

@item @var{value}.force_shwi () | |

Forcibly convert each coefficient of @samp{poly_int<@var{N}, @var{T}>} | |

@var{value} to @code{HOST_WIDE_INT}, truncating any that are out of range. | |

Return the result as a @samp{poly_int<@var{N}, @code{HOST_WIDE_INT}>}. | |

@item @var{value}.force_uhwi () | |

Forcibly convert each coefficient of @samp{poly_int<@var{N}, @var{T}>} | |

@var{value} to @code{unsigned HOST_WIDE_INT}, truncating any that are | |

out of range. Return the result as a | |

@samp{poly_int<@var{N}, @code{unsigned HOST_WIDE_INT}>}. | |

@item wi::shwi (@var{value}, @var{precision}) | |

Return a @code{poly_int} with the same value as @var{value}, but with | |

the coefficients converted from @code{HOST_WIDE_INT} to @code{wide_int}. | |

@var{precision} specifies the precision of the @code{wide_int} cofficients; | |

if this is wider than a @code{HOST_WIDE_INT}, the coefficients of | |

@var{value} will be sign-extended to fit. | |

@item wi::uhwi (@var{value}, @var{precision}) | |

Like @code{wi::shwi}, except that @var{value} has coefficients of | |

type @code{unsigned HOST_WIDE_INT}. If @var{precision} is wider than | |

a @code{HOST_WIDE_INT}, the coefficients of @var{value} will be | |

zero-extended to fit. | |

@item wi::sext (@var{value}, @var{precision}) | |

Return a @code{poly_int} of the same type as @var{value}, sign-extending | |

every coefficient from the low @var{precision} bits. This in effect | |

applies @code{wi::sext} to each coefficient individually. | |

@item wi::zext (@var{value}, @var{precision}) | |

Like @code{wi::sext}, but for zero extension. | |

@item poly_wide_int::from (@var{value}, @var{precision}, @var{sign}) | |

Convert @var{value} to a @code{poly_wide_int} in which each coefficient | |

has @var{precision} bits. Extend the coefficients according to | |

@var{sign} if the coefficients have fewer bits. | |

@item poly_offset_int::from (@var{value}, @var{sign}) | |

Convert @var{value} to a @code{poly_offset_int}, extending its coefficients | |

according to @var{sign} if they have fewer bits than @code{offset_int}. | |

@item poly_widest_int::from (@var{value}, @var{sign}) | |

Convert @var{value} to a @code{poly_widest_int}, extending its coefficients | |

according to @var{sign} if they have fewer bits than @code{widest_int}. | |

@end table | |

@node Miscellaneous @code{poly_int} routines | |

@section Miscellaneous @code{poly_int} routines | |

@table @samp | |

@item print_dec (@var{value}, @var{file}, @var{sign}) | |

@itemx print_dec (@var{value}, @var{file}) | |

Print @var{value} to @var{file} as a decimal value, interpreting | |

the coefficients according to @var{sign}. The final argument is | |

optional if @var{value} has an inherent sign; for example, | |

@code{poly_int64} values print as signed by default and | |

@code{poly_uint64} values print as unsigned by default. | |

This is a simply a @code{poly_int} version of a wide-int routine. | |

@end table | |

@node Guidelines for using @code{poly_int} | |

@section Guidelines for using @code{poly_int} | |

One of the main design goals of @code{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: | |

@itemize | |

@item | |

The set of @code{poly_int} operations should be complete enough that | |

the question in most cases becomes ``Can we do this operation on these | |

particular @code{poly_int} values? If not, bail out'' rather than | |

``Are these @code{poly_int} values constant? If so, do the operation, | |

otherwise bail out''. | |

@item | |

If target-independent code compiles and runs correctly on a target | |

with one value of @code{NUM_POLY_INT_COEFFS}, and if the code does not | |

use asserting functions like @code{to_constant}, it is reasonable to | |

assume that the code also works on targets with other values of | |

@code{NUM_POLY_INT_COEFFS}. There is no need to check this during | |

everyday development. | |

@end itemize | |

So the general principle is: if target-independent code is dealing | |

with a @code{poly_int} value, it is better to operate on it as a | |

@code{poly_int} if at all possible, choosing conservatively-correct | |

behavior if a particular operation fails. For example, the following | |

code handles an index @code{pos} into a sequence of vectors that each | |

have @code{nunits} elements: | |

@smallexample | |

/* 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; | |

@} | |

@end smallexample | |

However, there are some contexts in which operating on a | |

@code{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: | |

@smallexample | |

if (@var{poly_value}.is_constant (&@var{const_value})) | |

@{ | |

@dots{} | |

/* Operate on @var{const_value}. */ | |

@dots{} | |

@} | |

else | |

@{ | |

@dots{} | |

/* Conservatively correct fallback. */ | |

@dots{} | |

@} | |

@end smallexample | |

@code{poly_int} also provides some asserting functions like | |

@code{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 @code{is_constant}, in which case the implementation phase can | |

reasonably use @code{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 | |

@code{poly_int} version if a user hits the assertion. | |

If a particular asserting function like @code{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: | |

@smallexample | |

/* 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 ()) | |

@end smallexample | |

Target-specific code in @file{config/@var{cpu}} only needs to handle | |

non-constant @code{poly_int}s if @code{NUM_POLY_INT_COEFFS} is greater | |

than one. For other targets, @code{poly_int} degenerates to a compile-time | |

constant and is often interchangable with a normal scalar integer. | |

There are two main exceptions: | |

@itemize | |

@item | |

Sometimes an explicit cast to an integer type might be needed, such as to | |

resolve ambiguities in a @code{?:} expression, or when passing values | |

through @code{...} to things like print functions. | |

@item | |

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: | |

@itemize | |

@item | |

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

@item | |

Put the target's implementation of the target macro in its | |

@file{@var{cpu}.c} file and call it from the target macro in the | |

@file{@var{cpu}.h} file. | |

@item | |

Add @code{to_constant ()} calls where necessary. The previous option | |

is preferable because it will help with any future conversion of the | |

macro to a hook. | |

@end itemize | |

@end itemize | |