## Mercurial > hg > CbC > CbC_gcc

### view gcc/doc/poly-int.texi @ 158:494b0b89df80 default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

...

author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|

date | Mon, 25 May 2020 18:13:55 +0900 |

parents | 1830386684a0 |

children |

line wrap: on

line source

@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