18dd4bdcdSmrg@node poly_int 28dd4bdcdSmrg@chapter Sizes and offsets as runtime invariants 38dd4bdcdSmrg@cindex polynomial integers 48dd4bdcdSmrg@findex poly_int 58dd4bdcdSmrg 68dd4bdcdSmrgGCC allows the size of a hardware register to be a runtime invariant 78dd4bdcdSmrgrather than a compile-time constant. This in turn means that various 88dd4bdcdSmrgsizes and offsets must also be runtime invariants rather than 98dd4bdcdSmrgcompile-time constants, such as: 108dd4bdcdSmrg 118dd4bdcdSmrg@itemize @bullet 128dd4bdcdSmrg@item 138dd4bdcdSmrgthe size of a general @code{machine_mode} (@pxref{Machine Modes}); 148dd4bdcdSmrg 158dd4bdcdSmrg@item 168dd4bdcdSmrgthe size of a spill slot; 178dd4bdcdSmrg 188dd4bdcdSmrg@item 198dd4bdcdSmrgthe offset of something within a stack frame; 208dd4bdcdSmrg 218dd4bdcdSmrg@item 228dd4bdcdSmrgthe number of elements in a vector; 238dd4bdcdSmrg 248dd4bdcdSmrg@item 258dd4bdcdSmrgthe size and offset of a @code{mem} rtx (@pxref{Regs and Memory}); and 268dd4bdcdSmrg 278dd4bdcdSmrg@item 288dd4bdcdSmrgthe byte offset in a @code{subreg} rtx (@pxref{Regs and Memory}). 298dd4bdcdSmrg@end itemize 308dd4bdcdSmrg 318dd4bdcdSmrgThe motivating example is the Arm SVE ISA, whose vector registers can be 328dd4bdcdSmrgany multiple of 128 bits between 128 and 2048 inclusive. The compiler 338dd4bdcdSmrgnormally produces code that works for all SVE register sizes, with the 348dd4bdcdSmrgactual size only being known at runtime. 358dd4bdcdSmrg 368dd4bdcdSmrgGCC's main representation of such runtime invariants is the 378dd4bdcdSmrg@code{poly_int} class. This chapter describes what @code{poly_int} 388dd4bdcdSmrgdoes, lists the available operations, and gives some general 398dd4bdcdSmrgusage guidelines. 408dd4bdcdSmrg 418dd4bdcdSmrg@menu 428dd4bdcdSmrg* Overview of @code{poly_int}:: 438dd4bdcdSmrg* Consequences of using @code{poly_int}:: 448dd4bdcdSmrg* Comparisons involving @code{poly_int}:: 458dd4bdcdSmrg* Arithmetic on @code{poly_int}s:: 468dd4bdcdSmrg* Alignment of @code{poly_int}s:: 478dd4bdcdSmrg* Computing bounds on @code{poly_int}s:: 488dd4bdcdSmrg* Converting @code{poly_int}s:: 498dd4bdcdSmrg* Miscellaneous @code{poly_int} routines:: 508dd4bdcdSmrg* Guidelines for using @code{poly_int}:: 518dd4bdcdSmrg@end menu 528dd4bdcdSmrg 538dd4bdcdSmrg@node Overview of @code{poly_int} 548dd4bdcdSmrg@section Overview of @code{poly_int} 558dd4bdcdSmrg 568dd4bdcdSmrg@cindex @code{poly_int}, runtime value 578dd4bdcdSmrgWe define indeterminates @var{x1}, @dots{}, @var{xn} whose values are 588dd4bdcdSmrgonly known at runtime and use polynomials of the form: 598dd4bdcdSmrg 608dd4bdcdSmrg@smallexample 618dd4bdcdSmrg@var{c0} + @var{c1} * @var{x1} + @dots{} + @var{cn} * @var{xn} 628dd4bdcdSmrg@end smallexample 638dd4bdcdSmrg 648dd4bdcdSmrgto represent a size or offset whose value might depend on some 658dd4bdcdSmrgof these indeterminates. The coefficients @var{c0}, @dots{}, @var{cn} 668dd4bdcdSmrgare always known at compile time, with the @var{c0} term being the 678dd4bdcdSmrg``constant'' part that does not depend on any runtime value. 688dd4bdcdSmrg 698dd4bdcdSmrgGCC uses the @code{poly_int} class to represent these coefficients. 708dd4bdcdSmrgThe class has two template parameters: the first specifies the number of 718dd4bdcdSmrgcoefficients (@var{n} + 1) and the second specifies the type of the 728dd4bdcdSmrgcoefficients. For example, @samp{poly_int<2, unsigned short>} represents 738dd4bdcdSmrga polynomial with two coefficients (and thus one indeterminate), with each 748dd4bdcdSmrgcoefficient having type @code{unsigned short}. When @var{n} is 0, 758dd4bdcdSmrgthe class degenerates to a single compile-time constant @var{c0}. 768dd4bdcdSmrg 778dd4bdcdSmrg@cindex @code{poly_int}, template parameters 788dd4bdcdSmrg@findex NUM_POLY_INT_COEFFS 798dd4bdcdSmrgThe number of coefficients needed for compilation is a fixed 808dd4bdcdSmrgproperty of each target and is specified by the configuration macro 818dd4bdcdSmrg@code{NUM_POLY_INT_COEFFS}. The default value is 1, since most targets 828dd4bdcdSmrgdo not have such runtime invariants. Targets that need a different 838dd4bdcdSmrgvalue should @code{#define} the macro in their @file{@var{cpu}-modes.def} 848dd4bdcdSmrgfile. @xref{Back End}. 858dd4bdcdSmrg 868dd4bdcdSmrg@cindex @code{poly_int}, invariant range 878dd4bdcdSmrg@code{poly_int} makes the simplifying requirement that each indeterminate 888dd4bdcdSmrgmust be a nonnegative integer. An indeterminate value of 0 should usually 898dd4bdcdSmrgrepresent the minimum possible runtime value, with @var{c0} specifying 908dd4bdcdSmrgthe value in that case. 918dd4bdcdSmrg 928dd4bdcdSmrgFor example, when targetting the Arm SVE ISA, the single indeterminate 938dd4bdcdSmrgrepresents the number of 128-bit blocks in a vector @emph{beyond the minimum 948dd4bdcdSmrglength of 128 bits}. Thus the number of 64-bit doublewords in a vector 958dd4bdcdSmrgis 2 + 2 * @var{x1}. If an aggregate has a single SVE vector and 16 968dd4bdcdSmrgadditional bytes, its total size is 32 + 16 * @var{x1} bytes. 978dd4bdcdSmrg 988dd4bdcdSmrgThe header file @file{poly-int-types.h} provides typedefs for the 998dd4bdcdSmrgmost common forms of @code{poly_int}, all having 1008dd4bdcdSmrg@code{NUM_POLY_INT_COEFFS} coefficients: 1018dd4bdcdSmrg 1028dd4bdcdSmrg@cindex @code{poly_int}, main typedefs 1038dd4bdcdSmrg@table @code 1048dd4bdcdSmrg@item poly_uint16 1058dd4bdcdSmrga @samp{poly_int} with @code{unsigned short} coefficients. 1068dd4bdcdSmrg 1078dd4bdcdSmrg@item poly_int64 1088dd4bdcdSmrga @samp{poly_int} with @code{HOST_WIDE_INT} coefficients. 1098dd4bdcdSmrg 1108dd4bdcdSmrg@item poly_uint64 1118dd4bdcdSmrga @samp{poly_int} with @code{unsigned HOST_WIDE_INT} coefficients. 1128dd4bdcdSmrg 1138dd4bdcdSmrg@item poly_offset_int 1148dd4bdcdSmrga @samp{poly_int} with @code{offset_int} coefficients. 1158dd4bdcdSmrg 1168dd4bdcdSmrg@item poly_wide_int 1178dd4bdcdSmrga @samp{poly_int} with @code{wide_int} coefficients. 1188dd4bdcdSmrg 1198dd4bdcdSmrg@item poly_widest_int 1208dd4bdcdSmrga @samp{poly_int} with @code{widest_int} coefficients. 1218dd4bdcdSmrg@end table 1228dd4bdcdSmrg 1238dd4bdcdSmrgSince the main purpose of @code{poly_int} is to represent sizes and 1248dd4bdcdSmrgoffsets, the last two typedefs are only rarely used. 1258dd4bdcdSmrg 1268dd4bdcdSmrg@node Consequences of using @code{poly_int} 1278dd4bdcdSmrg@section Consequences of using @code{poly_int} 1288dd4bdcdSmrg 1298dd4bdcdSmrgThe two main consequences of using polynomial sizes and offsets are that: 1308dd4bdcdSmrg 1318dd4bdcdSmrg@itemize 1328dd4bdcdSmrg@item 1338dd4bdcdSmrgthere is no total ordering between the values at compile time, and 1348dd4bdcdSmrg 1358dd4bdcdSmrg@item 1368dd4bdcdSmrgsome operations might yield results that cannot be expressed as a 1378dd4bdcdSmrg@code{poly_int}. 1388dd4bdcdSmrg@end itemize 1398dd4bdcdSmrg 1408dd4bdcdSmrgFor example, if @var{x} is a runtime invariant, we cannot tell at 1418dd4bdcdSmrgcompile time whether: 1428dd4bdcdSmrg 1438dd4bdcdSmrg@smallexample 1448dd4bdcdSmrg3 + 4@var{x} <= 1 + 5@var{x} 1458dd4bdcdSmrg@end smallexample 1468dd4bdcdSmrg 1478dd4bdcdSmrgsince the condition is false when @var{x} <= 1 and true when @var{x} >= 2. 1488dd4bdcdSmrg 1498dd4bdcdSmrgSimilarly, @code{poly_int} cannot represent the result of: 1508dd4bdcdSmrg 1518dd4bdcdSmrg@smallexample 1528dd4bdcdSmrg(3 + 4@var{x}) * (1 + 5@var{x}) 1538dd4bdcdSmrg@end smallexample 1548dd4bdcdSmrg 1558dd4bdcdSmrgsince it cannot (and in practice does not need to) store powers greater 1568dd4bdcdSmrgthan one. It also cannot represent the result of: 1578dd4bdcdSmrg 1588dd4bdcdSmrg@smallexample 1598dd4bdcdSmrg(3 + 4@var{x}) / (1 + 5@var{x}) 1608dd4bdcdSmrg@end smallexample 1618dd4bdcdSmrg 1628dd4bdcdSmrgThe following sections describe how we deal with these restrictions. 1638dd4bdcdSmrg 1648dd4bdcdSmrg@cindex @code{poly_int}, use in target-independent code 1658dd4bdcdSmrgAs described earlier, a @code{poly_int<1, @var{T}>} has no indeterminates 1668dd4bdcdSmrgand so degenerates to a compile-time constant of type @var{T}. It would 1678dd4bdcdSmrgbe possible in that case to do all normal arithmetic on the @var{T}, 1688dd4bdcdSmrgand to compare the @var{T} using the normal C++ operators. We deliberately 1698dd4bdcdSmrgprevent target-independent code from doing this, since the compiler needs 1708dd4bdcdSmrgto support other @code{poly_int<@var{n}, @var{T}>} as well, regardless of 1718dd4bdcdSmrgthe current target's @code{NUM_POLY_INT_COEFFS}. 1728dd4bdcdSmrg 1738dd4bdcdSmrg@cindex @code{poly_int}, use in target-specific code 1748dd4bdcdSmrgHowever, it would be very artificial to force target-specific code 1758dd4bdcdSmrgto follow these restrictions if the target has no runtime indeterminates. 1768dd4bdcdSmrgThere is therefore an implicit conversion from @code{poly_int<1, @var{T}>} 1778dd4bdcdSmrgto @var{T} when compiling target-specific translation units. 1788dd4bdcdSmrg 1798dd4bdcdSmrg@node Comparisons involving @code{poly_int} 1808dd4bdcdSmrg@section Comparisons involving @code{poly_int} 1818dd4bdcdSmrg 1828dd4bdcdSmrgIn general we need to compare sizes and offsets in two situations: 1838dd4bdcdSmrgthose in which the values need to be ordered, and those in which 1848dd4bdcdSmrgthe values can be unordered. More loosely, the distinction is often 1858dd4bdcdSmrgbetween values that have a definite link (usually because they refer to the 1868dd4bdcdSmrgsame underlying register or memory location) and values that have 1878dd4bdcdSmrgno definite link. An example of the former is the relationship between 1888dd4bdcdSmrgthe inner and outer sizes of a subreg, where we must know at compile time 1898dd4bdcdSmrgwhether the subreg is paradoxical, partial, or complete. An example of 1908dd4bdcdSmrgthe latter is alias analysis: we might want to check whether two 1918dd4bdcdSmrgarbitrary memory references overlap. 1928dd4bdcdSmrg 1938dd4bdcdSmrgReferring back to the examples in the previous section, it makes sense 1948dd4bdcdSmrgto ask whether a memory reference of size @samp{3 + 4@var{x}} overlaps 1958dd4bdcdSmrgone of size @samp{1 + 5@var{x}}, but it does not make sense to have a 1968dd4bdcdSmrgsubreg in which the outer mode has @samp{3 + 4@var{x}} bytes and the 1978dd4bdcdSmrginner mode has @samp{1 + 5@var{x}} bytes (or vice versa). Such subregs 1988dd4bdcdSmrgare always invalid and should trigger an internal compiler error 1998dd4bdcdSmrgif formed. 2008dd4bdcdSmrg 2018dd4bdcdSmrgThe underlying operators are the same in both cases, but the distinction 2028dd4bdcdSmrgaffects how they are used. 2038dd4bdcdSmrg 2048dd4bdcdSmrg@menu 2058dd4bdcdSmrg* Comparison functions for @code{poly_int}:: 2068dd4bdcdSmrg* Properties of the @code{poly_int} comparisons:: 2078dd4bdcdSmrg* Comparing potentially-unordered @code{poly_int}s:: 2088dd4bdcdSmrg* Comparing ordered @code{poly_int}s:: 2098dd4bdcdSmrg* Checking for a @code{poly_int} marker value:: 2108dd4bdcdSmrg* Range checks on @code{poly_int}s:: 2118dd4bdcdSmrg* Sorting @code{poly_int}s:: 2128dd4bdcdSmrg@end menu 2138dd4bdcdSmrg 2148dd4bdcdSmrg@node Comparison functions for @code{poly_int} 2158dd4bdcdSmrg@subsection Comparison functions for @code{poly_int} 2168dd4bdcdSmrg 2178dd4bdcdSmrg@code{poly_int} provides the following routines for checking whether 2188dd4bdcdSmrga particular condition ``may be'' (might be) true: 2198dd4bdcdSmrg 2208dd4bdcdSmrg@example 2218dd4bdcdSmrgmaybe_lt maybe_le maybe_eq maybe_ge maybe_gt 2228dd4bdcdSmrg maybe_ne 2238dd4bdcdSmrg@end example 2248dd4bdcdSmrg 2258dd4bdcdSmrgThe functions have their natural meaning: 2268dd4bdcdSmrg 2278dd4bdcdSmrg@table @samp 2288dd4bdcdSmrg@item maybe_lt(@var{a}, @var{b}) 2298dd4bdcdSmrgReturn true if @var{a} might be less than @var{b}. 2308dd4bdcdSmrg 2318dd4bdcdSmrg@item maybe_le(@var{a}, @var{b}) 2328dd4bdcdSmrgReturn true if @var{a} might be less than or equal to @var{b}. 2338dd4bdcdSmrg 2348dd4bdcdSmrg@item maybe_eq(@var{a}, @var{b}) 2358dd4bdcdSmrgReturn true if @var{a} might be equal to @var{b}. 2368dd4bdcdSmrg 2378dd4bdcdSmrg@item maybe_ne(@var{a}, @var{b}) 2388dd4bdcdSmrgReturn true if @var{a} might not be equal to @var{b}. 2398dd4bdcdSmrg 2408dd4bdcdSmrg@item maybe_ge(@var{a}, @var{b}) 2418dd4bdcdSmrgReturn true if @var{a} might be greater than or equal to @var{b}. 2428dd4bdcdSmrg 2438dd4bdcdSmrg@item maybe_gt(@var{a}, @var{b}) 2448dd4bdcdSmrgReturn true if @var{a} might be greater than @var{b}. 2458dd4bdcdSmrg@end table 2468dd4bdcdSmrg 2478dd4bdcdSmrgFor readability, @code{poly_int} also provides ``known'' inverses of these 2488dd4bdcdSmrgfunctions: 2498dd4bdcdSmrg 2508dd4bdcdSmrg@example 2518dd4bdcdSmrgknown_lt (@var{a}, @var{b}) == !maybe_ge (@var{a}, @var{b}) 2528dd4bdcdSmrgknown_le (@var{a}, @var{b}) == !maybe_gt (@var{a}, @var{b}) 2538dd4bdcdSmrgknown_eq (@var{a}, @var{b}) == !maybe_ne (@var{a}, @var{b}) 2548dd4bdcdSmrgknown_ge (@var{a}, @var{b}) == !maybe_lt (@var{a}, @var{b}) 2558dd4bdcdSmrgknown_gt (@var{a}, @var{b}) == !maybe_le (@var{a}, @var{b}) 2568dd4bdcdSmrgknown_ne (@var{a}, @var{b}) == !maybe_eq (@var{a}, @var{b}) 2578dd4bdcdSmrg@end example 2588dd4bdcdSmrg 2598dd4bdcdSmrg@node Properties of the @code{poly_int} comparisons 2608dd4bdcdSmrg@subsection Properties of the @code{poly_int} comparisons 2618dd4bdcdSmrg 2628dd4bdcdSmrgAll ``maybe'' relations except @code{maybe_ne} are transitive, so for example: 2638dd4bdcdSmrg 2648dd4bdcdSmrg@smallexample 2658dd4bdcdSmrgmaybe_lt (@var{a}, @var{b}) && maybe_lt (@var{b}, @var{c}) implies maybe_lt (@var{a}, @var{c}) 2668dd4bdcdSmrg@end smallexample 2678dd4bdcdSmrg 2688dd4bdcdSmrgfor all @var{a}, @var{b} and @var{c}. @code{maybe_lt}, @code{maybe_gt} 2698dd4bdcdSmrgand @code{maybe_ne} are irreflexive, so for example: 2708dd4bdcdSmrg 2718dd4bdcdSmrg@smallexample 2728dd4bdcdSmrg!maybe_lt (@var{a}, @var{a}) 2738dd4bdcdSmrg@end smallexample 2748dd4bdcdSmrg 2758dd4bdcdSmrgis true for all @var{a}. @code{maybe_le}, @code{maybe_eq} and @code{maybe_ge} 2768dd4bdcdSmrgare reflexive, so for example: 2778dd4bdcdSmrg 2788dd4bdcdSmrg@smallexample 2798dd4bdcdSmrgmaybe_le (@var{a}, @var{a}) 2808dd4bdcdSmrg@end smallexample 2818dd4bdcdSmrg 2828dd4bdcdSmrgis true for all @var{a}. @code{maybe_eq} and @code{maybe_ne} are symmetric, so: 2838dd4bdcdSmrg 2848dd4bdcdSmrg@smallexample 2858dd4bdcdSmrgmaybe_eq (@var{a}, @var{b}) == maybe_eq (@var{b}, @var{a}) 2868dd4bdcdSmrgmaybe_ne (@var{a}, @var{b}) == maybe_ne (@var{b}, @var{a}) 2878dd4bdcdSmrg@end smallexample 2888dd4bdcdSmrg 2898dd4bdcdSmrgfor all @var{a} and @var{b}. In addition: 2908dd4bdcdSmrg 2918dd4bdcdSmrg@smallexample 2928dd4bdcdSmrgmaybe_le (@var{a}, @var{b}) == maybe_lt (@var{a}, @var{b}) || maybe_eq (@var{a}, @var{b}) 2938dd4bdcdSmrgmaybe_ge (@var{a}, @var{b}) == maybe_gt (@var{a}, @var{b}) || maybe_eq (@var{a}, @var{b}) 2948dd4bdcdSmrgmaybe_lt (@var{a}, @var{b}) == maybe_gt (@var{b}, @var{a}) 2958dd4bdcdSmrgmaybe_le (@var{a}, @var{b}) == maybe_ge (@var{b}, @var{a}) 2968dd4bdcdSmrg@end smallexample 2978dd4bdcdSmrg 2988dd4bdcdSmrgHowever: 2998dd4bdcdSmrg 3008dd4bdcdSmrg@smallexample 3018dd4bdcdSmrgmaybe_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})] 3028dd4bdcdSmrgmaybe_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})] 3038dd4bdcdSmrg@end smallexample 3048dd4bdcdSmrg 3058dd4bdcdSmrgOne example is again @samp{@var{a} == 3 + 4@var{x}} 3068dd4bdcdSmrgand @samp{@var{b} == 1 + 5@var{x}}, where @samp{maybe_le (@var{a}, @var{b})}, 3078dd4bdcdSmrg@samp{maybe_ge (@var{a}, @var{b})} and @samp{maybe_ne (@var{a}, @var{b})} 3088dd4bdcdSmrgall hold. @code{maybe_le} and @code{maybe_ge} are therefore not antisymetric 3098dd4bdcdSmrgand do not form a partial order. 3108dd4bdcdSmrg 3118dd4bdcdSmrgFrom the above, it follows that: 3128dd4bdcdSmrg 3138dd4bdcdSmrg@itemize @bullet 3148dd4bdcdSmrg@item 3158dd4bdcdSmrgAll ``known'' relations except @code{known_ne} are transitive. 3168dd4bdcdSmrg 3178dd4bdcdSmrg@item 3188dd4bdcdSmrg@code{known_lt}, @code{known_ne} and @code{known_gt} are irreflexive. 3198dd4bdcdSmrg 3208dd4bdcdSmrg@item 3218dd4bdcdSmrg@code{known_le}, @code{known_eq} and @code{known_ge} are reflexive. 3228dd4bdcdSmrg@end itemize 3238dd4bdcdSmrg 3248dd4bdcdSmrgAlso: 3258dd4bdcdSmrg 3268dd4bdcdSmrg@smallexample 3278dd4bdcdSmrgknown_lt (@var{a}, @var{b}) == known_gt (@var{b}, @var{a}) 3288dd4bdcdSmrgknown_le (@var{a}, @var{b}) == known_ge (@var{b}, @var{a}) 3298dd4bdcdSmrgknown_lt (@var{a}, @var{b}) implies !known_lt (@var{b}, @var{a}) [asymmetry] 3308dd4bdcdSmrgknown_gt (@var{a}, @var{b}) implies !known_gt (@var{b}, @var{a}) 3318dd4bdcdSmrgknown_le (@var{a}, @var{b}) && known_le (@var{b}, @var{a}) == known_eq (@var{a}, @var{b}) [== !maybe_ne (@var{a}, @var{b})] 3328dd4bdcdSmrgknown_ge (@var{a}, @var{b}) && known_ge (@var{b}, @var{a}) == known_eq (@var{a}, @var{b}) [== !maybe_ne (@var{a}, @var{b})] 3338dd4bdcdSmrg@end smallexample 3348dd4bdcdSmrg 3358dd4bdcdSmrg@code{known_le} and @code{known_ge} are therefore antisymmetric and are 3368dd4bdcdSmrgpartial orders. However: 3378dd4bdcdSmrg 3388dd4bdcdSmrg@smallexample 3398dd4bdcdSmrgknown_le (@var{a}, @var{b}) does not imply known_lt (@var{a}, @var{b}) || known_eq (@var{a}, @var{b}) 3408dd4bdcdSmrgknown_ge (@var{a}, @var{b}) does not imply known_gt (@var{a}, @var{b}) || known_eq (@var{a}, @var{b}) 3418dd4bdcdSmrg@end smallexample 3428dd4bdcdSmrg 3438dd4bdcdSmrgFor example, @samp{known_le (4, 4 + 4@var{x})} holds because the runtime 3448dd4bdcdSmrgindeterminate @var{x} is a nonnegative integer, but neither 3458dd4bdcdSmrg@code{known_lt (4, 4 + 4@var{x})} nor @code{known_eq (4, 4 + 4@var{x})} hold. 3468dd4bdcdSmrg 3478dd4bdcdSmrg@node Comparing potentially-unordered @code{poly_int}s 3488dd4bdcdSmrg@subsection Comparing potentially-unordered @code{poly_int}s 3498dd4bdcdSmrg 3508dd4bdcdSmrgIn cases where there is no definite link between two @code{poly_int}s, 3518dd4bdcdSmrgwe can usually make a conservatively-correct assumption. For example, 3528dd4bdcdSmrgthe conservative assumption for alias analysis is that two references 3538dd4bdcdSmrg@emph{might} alias. 3548dd4bdcdSmrg 3558dd4bdcdSmrgOne way of checking whether [@var{begin1}, @var{end1}) might overlap 3568dd4bdcdSmrg[@var{begin2}, @var{end2}) using the @code{poly_int} comparisons is: 3578dd4bdcdSmrg 3588dd4bdcdSmrg@smallexample 3598dd4bdcdSmrgmaybe_gt (@var{end1}, @var{begin2}) && maybe_gt (@var{end2}, @var{begin1}) 3608dd4bdcdSmrg@end smallexample 3618dd4bdcdSmrg 3628dd4bdcdSmrgand another (equivalent) way is: 3638dd4bdcdSmrg 3648dd4bdcdSmrg@smallexample 3658dd4bdcdSmrg!(known_le (@var{end1}, @var{begin2}) || known_le (@var{end2}, @var{begin1})) 3668dd4bdcdSmrg@end smallexample 3678dd4bdcdSmrg 3688dd4bdcdSmrgHowever, in this particular example, it is better to use the range helper 3698dd4bdcdSmrgfunctions instead. @xref{Range checks on @code{poly_int}s}. 3708dd4bdcdSmrg 3718dd4bdcdSmrg@node Comparing ordered @code{poly_int}s 3728dd4bdcdSmrg@subsection Comparing ordered @code{poly_int}s 3738dd4bdcdSmrg 3748dd4bdcdSmrgIn cases where there is a definite link between two @code{poly_int}s, 3758dd4bdcdSmrgsuch as the outer and inner sizes of subregs, we usually require the sizes 3768dd4bdcdSmrgto be ordered by the @code{known_le} partial order. @code{poly_int} provides 3778dd4bdcdSmrgthe following utility functions for ordered values: 3788dd4bdcdSmrg 3798dd4bdcdSmrg@table @samp 3808dd4bdcdSmrg@item ordered_p (@var{a}, @var{b}) 3818dd4bdcdSmrgReturn true if @var{a} and @var{b} are ordered by the @code{known_le} 3828dd4bdcdSmrgpartial order. 3838dd4bdcdSmrg 3848dd4bdcdSmrg@item ordered_min (@var{a}, @var{b}) 3858dd4bdcdSmrgAssert that @var{a} and @var{b} are ordered by @code{known_le} and return the 3868dd4bdcdSmrgminimum of the two. When using this function, please add a comment explaining 3878dd4bdcdSmrgwhy the values are known to be ordered. 3888dd4bdcdSmrg 3898dd4bdcdSmrg@item ordered_max (@var{a}, @var{b}) 3908dd4bdcdSmrgAssert that @var{a} and @var{b} are ordered by @code{known_le} and return the 3918dd4bdcdSmrgmaximum of the two. When using this function, please add a comment explaining 3928dd4bdcdSmrgwhy the values are known to be ordered. 3938dd4bdcdSmrg@end table 3948dd4bdcdSmrg 3958dd4bdcdSmrgFor example, if a subreg has an outer mode of size @var{outer} and an 3968dd4bdcdSmrginner mode of size @var{inner}: 3978dd4bdcdSmrg 3988dd4bdcdSmrg@itemize @bullet 3998dd4bdcdSmrg@item 4008dd4bdcdSmrgthe subreg is complete if known_eq (@var{inner}, @var{outer}) 4018dd4bdcdSmrg 4028dd4bdcdSmrg@item 4038dd4bdcdSmrgotherwise, the subreg is paradoxical if known_le (@var{inner}, @var{outer}) 4048dd4bdcdSmrg 4058dd4bdcdSmrg@item 4068dd4bdcdSmrgotherwise, the subreg is partial if known_le (@var{outer}, @var{inner}) 4078dd4bdcdSmrg 4088dd4bdcdSmrg@item 4098dd4bdcdSmrgotherwise, the subreg is ill-formed 4108dd4bdcdSmrg@end itemize 4118dd4bdcdSmrg 4128dd4bdcdSmrgThus the subreg is only valid if 4138dd4bdcdSmrg@samp{ordered_p (@var{outer}, @var{inner})} is true. If this condition 4148dd4bdcdSmrgis already known to be true then: 4158dd4bdcdSmrg 4168dd4bdcdSmrg@itemize @bullet 4178dd4bdcdSmrg@item 4188dd4bdcdSmrgthe subreg is complete if known_eq (@var{inner}, @var{outer}) 4198dd4bdcdSmrg 4208dd4bdcdSmrg@item 4218dd4bdcdSmrgthe subreg is paradoxical if maybe_lt (@var{inner}, @var{outer}) 4228dd4bdcdSmrg 4238dd4bdcdSmrg@item 4248dd4bdcdSmrgthe subreg is partial if maybe_lt (@var{outer}, @var{inner}) 4258dd4bdcdSmrg@end itemize 4268dd4bdcdSmrg 4278dd4bdcdSmrgwith the three conditions being mutually exclusive. 4288dd4bdcdSmrg 4298dd4bdcdSmrgCode that checks whether a subreg is valid would therefore generally 4308dd4bdcdSmrgcheck whether @code{ordered_p} holds (in addition to whatever other 4318dd4bdcdSmrgchecks are required for subreg validity). Code that is dealing 4328dd4bdcdSmrgwith existing subregs can assert that @code{ordered_p} holds 4338dd4bdcdSmrgand use either of the classifications above. 4348dd4bdcdSmrg 4358dd4bdcdSmrg@node Checking for a @code{poly_int} marker value 4368dd4bdcdSmrg@subsection Checking for a @code{poly_int} marker value 4378dd4bdcdSmrg 4388dd4bdcdSmrgIt is sometimes useful to have a special ``marker value'' that is not 4398dd4bdcdSmrgmeant to be taken literally. For example, some code uses a size 4408dd4bdcdSmrgof -1 to represent an unknown size, rather than having to carry around 4418dd4bdcdSmrga separate boolean to say whether the size is known. 4428dd4bdcdSmrg 4438dd4bdcdSmrgThe best way of checking whether something is a marker value is 4448dd4bdcdSmrg@code{known_eq}. Conversely the best way of checking whether something 4458dd4bdcdSmrgis @emph{not} a marker value is @code{maybe_ne}. 4468dd4bdcdSmrg 4478dd4bdcdSmrgThus in the size example just mentioned, @samp{known_eq (size, -1)} would 4488dd4bdcdSmrgcheck for an unknown size and @samp{maybe_ne (size, -1)} would check for a 4498dd4bdcdSmrgknown size. 4508dd4bdcdSmrg 4518dd4bdcdSmrg@node Range checks on @code{poly_int}s 4528dd4bdcdSmrg@subsection Range checks on @code{poly_int}s 4538dd4bdcdSmrg 4548dd4bdcdSmrgAs well as the core comparisons 4558dd4bdcdSmrg(@pxref{Comparison functions for @code{poly_int}}), @code{poly_int} provides 4568dd4bdcdSmrgutilities for various kinds of range check. In each case the range 4578dd4bdcdSmrgis represented by a start position and a size rather than a start 4588dd4bdcdSmrgposition and an end position; this is because the former is used 4598dd4bdcdSmrgmuch more often than the latter in GCC@. Also, the sizes can be 4608dd4bdcdSmrg-1 (or all ones for unsigned sizes) to indicate a range with a known 4618dd4bdcdSmrgstart position but an unknown size. All other sizes must be nonnegative. 4628dd4bdcdSmrgA range of size 0 does not contain anything or overlap anything. 4638dd4bdcdSmrg 4648dd4bdcdSmrg@table @samp 4658dd4bdcdSmrg@item known_size_p (@var{size}) 4668dd4bdcdSmrgReturn true if @var{size} represents a known range size, false if it 4678dd4bdcdSmrgis -1 or all ones (for signed and unsigned types respectively). 4688dd4bdcdSmrg 4698dd4bdcdSmrg@item ranges_maybe_overlap_p (@var{pos1}, @var{size1}, @var{pos2}, @var{size2}) 4708dd4bdcdSmrgReturn true if the range described by @var{pos1} and @var{size1} @emph{might} 4718dd4bdcdSmrgoverlap the range described by @var{pos2} and @var{size2} (in other words, 4728dd4bdcdSmrgreturn true if we cannot prove that the ranges are disjoint). 4738dd4bdcdSmrg 4748dd4bdcdSmrg@item ranges_known_overlap_p (@var{pos1}, @var{size1}, @var{pos2}, @var{size2}) 4758dd4bdcdSmrgReturn true if the range described by @var{pos1} and @var{size1} is known to 4768dd4bdcdSmrgoverlap the range described by @var{pos2} and @var{size2}. 4778dd4bdcdSmrg 4788dd4bdcdSmrg@item known_subrange_p (@var{pos1}, @var{size1}, @var{pos2}, @var{size2}) 4798dd4bdcdSmrgReturn true if the range described by @var{pos1} and @var{size1} is known to 4808dd4bdcdSmrgbe contained in the range described by @var{pos2} and @var{size2}. 4818dd4bdcdSmrg 4828dd4bdcdSmrg@item maybe_in_range_p (@var{value}, @var{pos}, @var{size}) 4838dd4bdcdSmrgReturn true if @var{value} @emph{might} be in the range described by 4848dd4bdcdSmrg@var{pos} and @var{size} (in other words, return true if we cannot 4858dd4bdcdSmrgprove that @var{value} is outside that range). 4868dd4bdcdSmrg 4878dd4bdcdSmrg@item known_in_range_p (@var{value}, @var{pos}, @var{size}) 4888dd4bdcdSmrgReturn true if @var{value} is known to be in the range described 4898dd4bdcdSmrgby @var{pos} and @var{size}. 4908dd4bdcdSmrg 4918dd4bdcdSmrg@item endpoint_representable_p (@var{pos}, @var{size}) 4928dd4bdcdSmrgReturn true if the range described by @var{pos} and @var{size} is 4938dd4bdcdSmrgopen-ended or if the endpoint (@var{pos} + @var{size}) is representable 4948dd4bdcdSmrgin the same type as @var{pos} and @var{size}. The function returns false 4958dd4bdcdSmrgif adding @var{size} to @var{pos} makes conceptual sense but could overflow. 4968dd4bdcdSmrg@end table 4978dd4bdcdSmrg 4988dd4bdcdSmrgThere is also a @code{poly_int} version of the @code{IN_RANGE_P} macro: 4998dd4bdcdSmrg 5008dd4bdcdSmrg@table @samp 5018dd4bdcdSmrg@item coeffs_in_range_p (@var{x}, @var{lower}, @var{upper}) 5028dd4bdcdSmrgReturn true if every coefficient of @var{x} is in the inclusive range 5038dd4bdcdSmrg[@var{lower}, @var{upper}]. This function can be useful when testing 5048dd4bdcdSmrgwhether an operation would cause the values of coefficients to 5058dd4bdcdSmrgoverflow. 5068dd4bdcdSmrg 5078dd4bdcdSmrgNote that the function does not indicate whether @var{x} itself is in the 5088dd4bdcdSmrggiven range. @var{x} can be either a constant or a @code{poly_int}. 5098dd4bdcdSmrg@end table 5108dd4bdcdSmrg 5118dd4bdcdSmrg@node Sorting @code{poly_int}s 5128dd4bdcdSmrg@subsection Sorting @code{poly_int}s 5138dd4bdcdSmrg 5148dd4bdcdSmrg@code{poly_int} provides the following routine for sorting: 5158dd4bdcdSmrg 5168dd4bdcdSmrg@table @samp 5178dd4bdcdSmrg@item compare_sizes_for_sort (@var{a}, @var{b}) 5188dd4bdcdSmrgCompare @var{a} and @var{b} in reverse lexicographical order (that is, 5198dd4bdcdSmrgcompare the highest-indexed coefficients first). This can be useful when 5208dd4bdcdSmrgsorting data structures, since it has the effect of separating constant 5218dd4bdcdSmrgand non-constant values. If all values are nonnegative, the constant 5228dd4bdcdSmrgvalues come first. 5238dd4bdcdSmrg 5248dd4bdcdSmrgNote that the values do not necessarily end up in numerical order. 5258dd4bdcdSmrgFor example, @samp{1 + 1@var{x}} would come after @samp{100} in the sort order, 5268dd4bdcdSmrgbut may well be less than @samp{100} at run time. 5278dd4bdcdSmrg@end table 5288dd4bdcdSmrg 5298dd4bdcdSmrg@node Arithmetic on @code{poly_int}s 5308dd4bdcdSmrg@section Arithmetic on @code{poly_int}s 5318dd4bdcdSmrg 5328dd4bdcdSmrgAddition, subtraction, negation and bit inversion all work normally for 5338dd4bdcdSmrg@code{poly_int}s. Multiplication by a constant multiplier and left 5348dd4bdcdSmrgshifting by a constant shift amount also work normally. General 5358dd4bdcdSmrgmultiplication of two @code{poly_int}s is not supported and is not 5368dd4bdcdSmrguseful in practice. 5378dd4bdcdSmrg 5388dd4bdcdSmrgOther operations are only conditionally supported: the operation 5398dd4bdcdSmrgmight succeed or might fail, depending on the inputs. 5408dd4bdcdSmrg 5418dd4bdcdSmrgThis section describes both types of operation. 5428dd4bdcdSmrg 5438dd4bdcdSmrg@menu 5448dd4bdcdSmrg* Using @code{poly_int} with C++ arithmetic operators:: 5458dd4bdcdSmrg* @code{wi} arithmetic on @code{poly_int}s:: 5468dd4bdcdSmrg* Division of @code{poly_int}s:: 5478dd4bdcdSmrg* Other @code{poly_int} arithmetic:: 5488dd4bdcdSmrg@end menu 5498dd4bdcdSmrg 5508dd4bdcdSmrg@node Using @code{poly_int} with C++ arithmetic operators 5518dd4bdcdSmrg@subsection Using @code{poly_int} with C++ arithmetic operators 5528dd4bdcdSmrg 5538dd4bdcdSmrgThe following C++ expressions are supported, where @var{p1} and @var{p2} 5548dd4bdcdSmrgare @code{poly_int}s and where @var{c1} and @var{c2} are scalars: 5558dd4bdcdSmrg 5568dd4bdcdSmrg@smallexample 5578dd4bdcdSmrg-@var{p1} 5588dd4bdcdSmrg~@var{p1} 5598dd4bdcdSmrg 5608dd4bdcdSmrg@var{p1} + @var{p2} 5618dd4bdcdSmrg@var{p1} + @var{c2} 5628dd4bdcdSmrg@var{c1} + @var{p2} 5638dd4bdcdSmrg 5648dd4bdcdSmrg@var{p1} - @var{p2} 5658dd4bdcdSmrg@var{p1} - @var{c2} 5668dd4bdcdSmrg@var{c1} - @var{p2} 5678dd4bdcdSmrg 5688dd4bdcdSmrg@var{c1} * @var{p2} 5698dd4bdcdSmrg@var{p1} * @var{c2} 5708dd4bdcdSmrg 5718dd4bdcdSmrg@var{p1} << @var{c2} 5728dd4bdcdSmrg 5738dd4bdcdSmrg@var{p1} += @var{p2} 5748dd4bdcdSmrg@var{p1} += @var{c2} 5758dd4bdcdSmrg 5768dd4bdcdSmrg@var{p1} -= @var{p2} 5778dd4bdcdSmrg@var{p1} -= @var{c2} 5788dd4bdcdSmrg 5798dd4bdcdSmrg@var{p1} *= @var{c2} 5808dd4bdcdSmrg@var{p1} <<= @var{c2} 5818dd4bdcdSmrg@end smallexample 5828dd4bdcdSmrg 5838dd4bdcdSmrgThese arithmetic operations handle integer ranks in a similar way 5848dd4bdcdSmrgto C++. The main difference is that every coefficient narrower than 5858dd4bdcdSmrg@code{HOST_WIDE_INT} promotes to @code{HOST_WIDE_INT}, whereas in 5868dd4bdcdSmrgC++ everything narrower than @code{int} promotes to @code{int}. 5878dd4bdcdSmrgFor example: 5888dd4bdcdSmrg 5898dd4bdcdSmrg@smallexample 5908dd4bdcdSmrgpoly_uint16 + int -> poly_int64 5918dd4bdcdSmrgunsigned int + poly_uint16 -> poly_int64 5928dd4bdcdSmrgpoly_int64 + int -> poly_int64 5938dd4bdcdSmrgpoly_int32 + poly_uint64 -> poly_uint64 5948dd4bdcdSmrguint64 + poly_int64 -> poly_uint64 5958dd4bdcdSmrgpoly_offset_int + int32 -> poly_offset_int 5968dd4bdcdSmrgoffset_int + poly_uint16 -> poly_offset_int 5978dd4bdcdSmrg@end smallexample 5988dd4bdcdSmrg 5998dd4bdcdSmrgIn the first two examples, both coefficients are narrower than 6008dd4bdcdSmrg@code{HOST_WIDE_INT}, so the result has coefficients of type 6018dd4bdcdSmrg@code{HOST_WIDE_INT}. In the other examples, the coefficient 6028dd4bdcdSmrgwith the highest rank ``wins''. 6038dd4bdcdSmrg 6048dd4bdcdSmrgIf one of the operands is @code{wide_int} or @code{poly_wide_int}, 6058dd4bdcdSmrgthe rules are the same as for @code{wide_int} arithmetic. 6068dd4bdcdSmrg 6078dd4bdcdSmrg@node @code{wi} arithmetic on @code{poly_int}s 6088dd4bdcdSmrg@subsection @code{wi} arithmetic on @code{poly_int}s 6098dd4bdcdSmrg 6108dd4bdcdSmrgAs well as the C++ operators, @code{poly_int} supports the following 6118dd4bdcdSmrg@code{wi} routines: 6128dd4bdcdSmrg 6138dd4bdcdSmrg@smallexample 6148dd4bdcdSmrgwi::neg (@var{p1}, &@var{overflow}) 6158dd4bdcdSmrg 6168dd4bdcdSmrgwi::add (@var{p1}, @var{p2}) 6178dd4bdcdSmrgwi::add (@var{p1}, @var{c2}) 6188dd4bdcdSmrgwi::add (@var{c1}, @var{p1}) 6198dd4bdcdSmrgwi::add (@var{p1}, @var{p2}, @var{sign}, &@var{overflow}) 6208dd4bdcdSmrg 6218dd4bdcdSmrgwi::sub (@var{p1}, @var{p2}) 6228dd4bdcdSmrgwi::sub (@var{p1}, @var{c2}) 6238dd4bdcdSmrgwi::sub (@var{c1}, @var{p1}) 6248dd4bdcdSmrgwi::sub (@var{p1}, @var{p2}, @var{sign}, &@var{overflow}) 6258dd4bdcdSmrg 6268dd4bdcdSmrgwi::mul (@var{p1}, @var{c2}) 6278dd4bdcdSmrgwi::mul (@var{c1}, @var{p1}) 6288dd4bdcdSmrgwi::mul (@var{p1}, @var{c2}, @var{sign}, &@var{overflow}) 6298dd4bdcdSmrg 6308dd4bdcdSmrgwi::lshift (@var{p1}, @var{c2}) 6318dd4bdcdSmrg@end smallexample 6328dd4bdcdSmrg 6338dd4bdcdSmrgThese routines just check whether overflow occurs on any individual 6348dd4bdcdSmrgcoefficient; it is not possible to know at compile time whether the 6358dd4bdcdSmrgfinal runtime value would overflow. 6368dd4bdcdSmrg 6378dd4bdcdSmrg@node Division of @code{poly_int}s 6388dd4bdcdSmrg@subsection Division of @code{poly_int}s 6398dd4bdcdSmrg 6408dd4bdcdSmrgDivision of @code{poly_int}s is possible for certain inputs. The functions 6418dd4bdcdSmrgfor division return true if the operation is possible and in most cases 6428dd4bdcdSmrgreturn the results by pointer. The routines are: 6438dd4bdcdSmrg 6448dd4bdcdSmrg@table @samp 6458dd4bdcdSmrg@item multiple_p (@var{a}, @var{b}) 6468dd4bdcdSmrg@itemx multiple_p (@var{a}, @var{b}, &@var{quotient}) 6478dd4bdcdSmrgReturn true if @var{a} is an exact multiple of @var{b}, storing the result 6488dd4bdcdSmrgin @var{quotient} if so. There are overloads for various combinations 6498dd4bdcdSmrgof polynomial and constant @var{a}, @var{b} and @var{quotient}. 6508dd4bdcdSmrg 6518dd4bdcdSmrg@item constant_multiple_p (@var{a}, @var{b}) 6528dd4bdcdSmrg@itemx constant_multiple_p (@var{a}, @var{b}, &@var{quotient}) 6538dd4bdcdSmrgLike @code{multiple_p}, but also test whether the multiple is a 6548dd4bdcdSmrgcompile-time constant. 6558dd4bdcdSmrg 6568dd4bdcdSmrg@item can_div_trunc_p (@var{a}, @var{b}, &@var{quotient}) 6578dd4bdcdSmrg@itemx can_div_trunc_p (@var{a}, @var{b}, &@var{quotient}, &@var{remainder}) 6588dd4bdcdSmrgReturn true if we can calculate @samp{trunc (@var{a} / @var{b})} at compile 6598dd4bdcdSmrgtime, storing the result in @var{quotient} and @var{remainder} if so. 6608dd4bdcdSmrg 6618dd4bdcdSmrg@item can_div_away_from_zero_p (@var{a}, @var{b}, &@var{quotient}) 6628dd4bdcdSmrgReturn true if we can calculate @samp{@var{a} / @var{b}} at compile time, 6638dd4bdcdSmrgrounding away from zero. Store the result in @var{quotient} if so. 6648dd4bdcdSmrg 6658dd4bdcdSmrgNote that this is true if and only if @code{can_div_trunc_p} is true. 6668dd4bdcdSmrgThe only difference is in the rounding of the result. 6678dd4bdcdSmrg@end table 6688dd4bdcdSmrg 6698dd4bdcdSmrgThere is also an asserting form of division: 6708dd4bdcdSmrg 6718dd4bdcdSmrg@table @samp 6728dd4bdcdSmrg@item exact_div (@var{a}, @var{b}) 6738dd4bdcdSmrgAssert that @var{a} is a multiple of @var{b} and return 6748dd4bdcdSmrg@samp{@var{a} / @var{b}}. The result is a @code{poly_int} if @var{a} 6758dd4bdcdSmrgis a @code{poly_int}. 6768dd4bdcdSmrg@end table 6778dd4bdcdSmrg 6788dd4bdcdSmrg@node Other @code{poly_int} arithmetic 6798dd4bdcdSmrg@subsection Other @code{poly_int} arithmetic 6808dd4bdcdSmrg 6818dd4bdcdSmrgThere are tentative routines for other operations besides division: 6828dd4bdcdSmrg 6838dd4bdcdSmrg@table @samp 6848dd4bdcdSmrg@item can_ior_p (@var{a}, @var{b}, &@var{result}) 6858dd4bdcdSmrgReturn true if we can calculate @samp{@var{a} | @var{b}} at compile time, 6868dd4bdcdSmrgstoring the result in @var{result} if so. 6878dd4bdcdSmrg@end table 6888dd4bdcdSmrg 6898dd4bdcdSmrgAlso, ANDs with a value @samp{(1 << @var{y}) - 1} or its inverse can be 6908dd4bdcdSmrgtreated as alignment operations. @xref{Alignment of @code{poly_int}s}. 6918dd4bdcdSmrg 6928dd4bdcdSmrgIn addition, the following miscellaneous routines are available: 6938dd4bdcdSmrg 6948dd4bdcdSmrg@table @samp 6958dd4bdcdSmrg@item coeff_gcd (@var{a}) 6968dd4bdcdSmrgReturn the greatest common divisor of all nonzero coefficients in 6978dd4bdcdSmrg@var{a}, or zero if @var{a} is known to be zero. 6988dd4bdcdSmrg 6998dd4bdcdSmrg@item common_multiple (@var{a}, @var{b}) 7008dd4bdcdSmrgReturn a value that is a multiple of both @var{a} and @var{b}, where 7018dd4bdcdSmrgone value is a @code{poly_int} and the other is a scalar. The result 7028dd4bdcdSmrgwill be the least common multiple for some indeterminate values but 7038dd4bdcdSmrgnot necessarily for all. 7048dd4bdcdSmrg 7058dd4bdcdSmrg@item force_common_multiple (@var{a}, @var{b}) 7068dd4bdcdSmrgReturn a value that is a multiple of both @code{poly_int} @var{a} and 7078dd4bdcdSmrg@code{poly_int} @var{b}, asserting that such a value exists. The 7088dd4bdcdSmrgresult will be the least common multiple for some indeterminate values 7098dd4bdcdSmrgbut not necessarily for all. 7108dd4bdcdSmrg 7118dd4bdcdSmrgWhen using this routine, please add a comment explaining why the 7128dd4bdcdSmrgassertion is known to hold. 7138dd4bdcdSmrg@end table 7148dd4bdcdSmrg 7158dd4bdcdSmrgPlease add any other operations that you find to be useful. 7168dd4bdcdSmrg 7178dd4bdcdSmrg@node Alignment of @code{poly_int}s 7188dd4bdcdSmrg@section Alignment of @code{poly_int}s 7198dd4bdcdSmrg 7208dd4bdcdSmrg@code{poly_int} provides various routines for aligning values and for querying 7218dd4bdcdSmrgmisalignments. In each case the alignment must be a power of 2. 7228dd4bdcdSmrg 7238dd4bdcdSmrg@table @samp 7248dd4bdcdSmrg@item can_align_p (@var{value}, @var{align}) 7258dd4bdcdSmrgReturn true if we can align @var{value} up or down to the nearest multiple 7268dd4bdcdSmrgof @var{align} at compile time. The answer is the same for both directions. 7278dd4bdcdSmrg 7288dd4bdcdSmrg@item can_align_down (@var{value}, @var{align}, &@var{aligned}) 7298dd4bdcdSmrgReturn true if @code{can_align_p}; if so, set @var{aligned} to the greatest 7308dd4bdcdSmrgaligned value that is less than or equal to @var{value}. 7318dd4bdcdSmrg 7328dd4bdcdSmrg@item can_align_up (@var{value}, @var{align}, &@var{aligned}) 7338dd4bdcdSmrgReturn true if @code{can_align_p}; if so, set @var{aligned} to the lowest 7348dd4bdcdSmrgaligned value that is greater than or equal to @var{value}. 7358dd4bdcdSmrg 7368dd4bdcdSmrg@item known_equal_after_align_down (@var{a}, @var{b}, @var{align}) 7378dd4bdcdSmrgReturn true if we can align @var{a} and @var{b} down to the nearest 7388dd4bdcdSmrg@var{align} boundary at compile time and if the two results are equal. 7398dd4bdcdSmrg 7408dd4bdcdSmrg@item known_equal_after_align_up (@var{a}, @var{b}, @var{align}) 7418dd4bdcdSmrgReturn true if we can align @var{a} and @var{b} up to the nearest 7428dd4bdcdSmrg@var{align} boundary at compile time and if the two results are equal. 7438dd4bdcdSmrg 7448dd4bdcdSmrg@item aligned_lower_bound (@var{value}, @var{align}) 7458dd4bdcdSmrgReturn a result that is no greater than @var{value} and that is aligned 7468dd4bdcdSmrgto @var{align}. The result will the closest aligned value for some 7478dd4bdcdSmrgindeterminate values but not necessarily for all. 7488dd4bdcdSmrg 7498dd4bdcdSmrgFor example, suppose we are allocating an object of @var{size} bytes 7508dd4bdcdSmrgin a downward-growing stack whose current limit is given by @var{limit}. 7518dd4bdcdSmrgIf the object requires @var{align} bytes of alignment, the new stack 7528dd4bdcdSmrglimit is given by: 7538dd4bdcdSmrg 7548dd4bdcdSmrg@smallexample 7558dd4bdcdSmrgaligned_lower_bound (@var{limit} - @var{size}, @var{align}) 7568dd4bdcdSmrg@end smallexample 7578dd4bdcdSmrg 7588dd4bdcdSmrg@item aligned_upper_bound (@var{value}, @var{align}) 7598dd4bdcdSmrgLikewise return a result that is no less than @var{value} and that is 7608dd4bdcdSmrgaligned to @var{align}. This is the routine that would be used for 7618dd4bdcdSmrgupward-growing stacks in the scenario just described. 7628dd4bdcdSmrg 7638dd4bdcdSmrg@item known_misalignment (@var{value}, @var{align}, &@var{misalign}) 7648dd4bdcdSmrgReturn true if we can calculate the misalignment of @var{value} 7658dd4bdcdSmrgwith respect to @var{align} at compile time, storing the result in 7668dd4bdcdSmrg@var{misalign} if so. 7678dd4bdcdSmrg 7688dd4bdcdSmrg@item known_alignment (@var{value}) 7698dd4bdcdSmrgReturn the minimum alignment that @var{value} is known to have 7708dd4bdcdSmrg(in other words, the largest alignment that can be guaranteed 7718dd4bdcdSmrgwhatever the values of the indeterminates turn out to be). 7728dd4bdcdSmrgReturn 0 if @var{value} is known to be 0. 7738dd4bdcdSmrg 7748dd4bdcdSmrg@item force_align_down (@var{value}, @var{align}) 7758dd4bdcdSmrgAssert that @var{value} can be aligned down to @var{align} at compile 7768dd4bdcdSmrgtime and return the result. When using this routine, please add a 7778dd4bdcdSmrgcomment explaining why the assertion is known to hold. 7788dd4bdcdSmrg 7798dd4bdcdSmrg@item force_align_up (@var{value}, @var{align}) 7808dd4bdcdSmrgLikewise, but aligning up. 7818dd4bdcdSmrg 7828dd4bdcdSmrg@item force_align_down_and_div (@var{value}, @var{align}) 7838dd4bdcdSmrgDivide the result of @code{force_align_down} by @var{align}. Again, 7848dd4bdcdSmrgplease add a comment explaining why the assertion in @code{force_align_down} 7858dd4bdcdSmrgis known to hold. 7868dd4bdcdSmrg 7878dd4bdcdSmrg@item force_align_up_and_div (@var{value}, @var{align}) 7888dd4bdcdSmrgLikewise for @code{force_align_up}. 7898dd4bdcdSmrg 7908dd4bdcdSmrg@item force_get_misalignment (@var{value}, @var{align}) 7918dd4bdcdSmrgAssert that we can calculate the misalignment of @var{value} with 7928dd4bdcdSmrgrespect to @var{align} at compile time and return the misalignment. 7938dd4bdcdSmrgWhen using this function, please add a comment explaining why 7948dd4bdcdSmrgthe assertion is known to hold. 7958dd4bdcdSmrg@end table 7968dd4bdcdSmrg 7978dd4bdcdSmrg@node Computing bounds on @code{poly_int}s 7988dd4bdcdSmrg@section Computing bounds on @code{poly_int}s 7998dd4bdcdSmrg 8008dd4bdcdSmrg@code{poly_int} also provides routines for calculating lower and upper bounds: 8018dd4bdcdSmrg 8028dd4bdcdSmrg@table @samp 8038dd4bdcdSmrg@item constant_lower_bound (@var{a}) 8048dd4bdcdSmrgAssert that @var{a} is nonnegative and return the smallest value it can have. 8058dd4bdcdSmrg 806*0bfacb9bSmrg@item constant_lower_bound_with_limit (@var{a}, @var{b}) 807*0bfacb9bSmrgReturn the least value @var{a} can have, given that the context in 808*0bfacb9bSmrgwhich @var{a} appears guarantees that the answer is no less than @var{b}. 809*0bfacb9bSmrgIn other words, the caller is asserting that @var{a} is greater than or 810*0bfacb9bSmrgequal to @var{b} even if @samp{known_ge (@var{a}, @var{b})} doesn't hold. 811*0bfacb9bSmrg 812*0bfacb9bSmrg@item constant_upper_bound_with_limit (@var{a}, @var{b}) 813*0bfacb9bSmrgReturn the greatest value @var{a} can have, given that the context in 814*0bfacb9bSmrgwhich @var{a} appears guarantees that the answer is no greater than @var{b}. 815*0bfacb9bSmrgIn other words, the caller is asserting that @var{a} is less than or equal 816*0bfacb9bSmrgto @var{b} even if @samp{known_le (@var{a}, @var{b})} doesn't hold. 817*0bfacb9bSmrg 8188dd4bdcdSmrg@item lower_bound (@var{a}, @var{b}) 8198dd4bdcdSmrgReturn a value that is always less than or equal to both @var{a} and @var{b}. 8208dd4bdcdSmrgIt will be the greatest such value for some indeterminate values 8218dd4bdcdSmrgbut necessarily for all. 8228dd4bdcdSmrg 8238dd4bdcdSmrg@item upper_bound (@var{a}, @var{b}) 8248dd4bdcdSmrgReturn a value that is always greater than or equal to both @var{a} and 8258dd4bdcdSmrg@var{b}. It will be the least such value for some indeterminate values 8268dd4bdcdSmrgbut necessarily for all. 8278dd4bdcdSmrg@end table 8288dd4bdcdSmrg 8298dd4bdcdSmrg@node Converting @code{poly_int}s 8308dd4bdcdSmrg@section Converting @code{poly_int}s 8318dd4bdcdSmrg 8328dd4bdcdSmrgA @code{poly_int<@var{n}, @var{T}>} can be constructed from up to 8338dd4bdcdSmrg@var{n} individual @var{T} coefficients, with the remaining coefficients 8348dd4bdcdSmrgbeing implicitly zero. In particular, this means that every 8358dd4bdcdSmrg@code{poly_int<@var{n}, @var{T}>} can be constructed from a single 8368dd4bdcdSmrgscalar @var{T}, or something compatible with @var{T}. 8378dd4bdcdSmrg 8388dd4bdcdSmrgAlso, a @code{poly_int<@var{n}, @var{T}>} can be constructed from 8398dd4bdcdSmrga @code{poly_int<@var{n}, @var{U}>} if @var{T} can be constructed 8408dd4bdcdSmrgfrom @var{U}. 8418dd4bdcdSmrg 8428dd4bdcdSmrgThe following functions provide other forms of conversion, 8438dd4bdcdSmrgor test whether such a conversion would succeed. 8448dd4bdcdSmrg 8458dd4bdcdSmrg@table @samp 8468dd4bdcdSmrg@item @var{value}.is_constant () 8478dd4bdcdSmrgReturn true if @code{poly_int} @var{value} is a compile-time constant. 8488dd4bdcdSmrg 8498dd4bdcdSmrg@item @var{value}.is_constant (&@var{c1}) 8508dd4bdcdSmrgReturn true if @code{poly_int} @var{value} is a compile-time constant, 8518dd4bdcdSmrgstoring it in @var{c1} if so. @var{c1} must be able to hold all 8528dd4bdcdSmrgconstant values of @var{value} without loss of precision. 8538dd4bdcdSmrg 8548dd4bdcdSmrg@item @var{value}.to_constant () 8558dd4bdcdSmrgAssert that @var{value} is a compile-time constant and return its value. 8568dd4bdcdSmrgWhen using this function, please add a comment explaining why the 8578dd4bdcdSmrgcondition is known to hold (for example, because an earlier phase 8588dd4bdcdSmrgof analysis rejected non-constants). 8598dd4bdcdSmrg 8608dd4bdcdSmrg@item @var{value}.to_shwi (&@var{p2}) 8618dd4bdcdSmrgReturn true if @samp{poly_int<@var{N}, @var{T}>} @var{value} can be 8628dd4bdcdSmrgrepresented without loss of precision as a 8638dd4bdcdSmrg@samp{poly_int<@var{N}, @code{HOST_WIDE_INT}>}, storing it in that 8648dd4bdcdSmrgform in @var{p2} if so. 8658dd4bdcdSmrg 8668dd4bdcdSmrg@item @var{value}.to_uhwi (&@var{p2}) 8678dd4bdcdSmrgReturn true if @samp{poly_int<@var{N}, @var{T}>} @var{value} can be 8688dd4bdcdSmrgrepresented without loss of precision as a 8698dd4bdcdSmrg@samp{poly_int<@var{N}, @code{unsigned HOST_WIDE_INT}>}, storing it in that 8708dd4bdcdSmrgform in @var{p2} if so. 8718dd4bdcdSmrg 8728dd4bdcdSmrg@item @var{value}.force_shwi () 8738dd4bdcdSmrgForcibly convert each coefficient of @samp{poly_int<@var{N}, @var{T}>} 8748dd4bdcdSmrg@var{value} to @code{HOST_WIDE_INT}, truncating any that are out of range. 8758dd4bdcdSmrgReturn the result as a @samp{poly_int<@var{N}, @code{HOST_WIDE_INT}>}. 8768dd4bdcdSmrg 8778dd4bdcdSmrg@item @var{value}.force_uhwi () 8788dd4bdcdSmrgForcibly convert each coefficient of @samp{poly_int<@var{N}, @var{T}>} 8798dd4bdcdSmrg@var{value} to @code{unsigned HOST_WIDE_INT}, truncating any that are 8808dd4bdcdSmrgout of range. Return the result as a 8818dd4bdcdSmrg@samp{poly_int<@var{N}, @code{unsigned HOST_WIDE_INT}>}. 8828dd4bdcdSmrg 8838dd4bdcdSmrg@item wi::shwi (@var{value}, @var{precision}) 8848dd4bdcdSmrgReturn a @code{poly_int} with the same value as @var{value}, but with 8858dd4bdcdSmrgthe coefficients converted from @code{HOST_WIDE_INT} to @code{wide_int}. 8868dd4bdcdSmrg@var{precision} specifies the precision of the @code{wide_int} cofficients; 8878dd4bdcdSmrgif this is wider than a @code{HOST_WIDE_INT}, the coefficients of 8888dd4bdcdSmrg@var{value} will be sign-extended to fit. 8898dd4bdcdSmrg 8908dd4bdcdSmrg@item wi::uhwi (@var{value}, @var{precision}) 8918dd4bdcdSmrgLike @code{wi::shwi}, except that @var{value} has coefficients of 8928dd4bdcdSmrgtype @code{unsigned HOST_WIDE_INT}. If @var{precision} is wider than 8938dd4bdcdSmrga @code{HOST_WIDE_INT}, the coefficients of @var{value} will be 8948dd4bdcdSmrgzero-extended to fit. 8958dd4bdcdSmrg 8968dd4bdcdSmrg@item wi::sext (@var{value}, @var{precision}) 8978dd4bdcdSmrgReturn a @code{poly_int} of the same type as @var{value}, sign-extending 8988dd4bdcdSmrgevery coefficient from the low @var{precision} bits. This in effect 8998dd4bdcdSmrgapplies @code{wi::sext} to each coefficient individually. 9008dd4bdcdSmrg 9018dd4bdcdSmrg@item wi::zext (@var{value}, @var{precision}) 9028dd4bdcdSmrgLike @code{wi::sext}, but for zero extension. 9038dd4bdcdSmrg 9048dd4bdcdSmrg@item poly_wide_int::from (@var{value}, @var{precision}, @var{sign}) 9058dd4bdcdSmrgConvert @var{value} to a @code{poly_wide_int} in which each coefficient 9068dd4bdcdSmrghas @var{precision} bits. Extend the coefficients according to 9078dd4bdcdSmrg@var{sign} if the coefficients have fewer bits. 9088dd4bdcdSmrg 9098dd4bdcdSmrg@item poly_offset_int::from (@var{value}, @var{sign}) 9108dd4bdcdSmrgConvert @var{value} to a @code{poly_offset_int}, extending its coefficients 9118dd4bdcdSmrgaccording to @var{sign} if they have fewer bits than @code{offset_int}. 9128dd4bdcdSmrg 9138dd4bdcdSmrg@item poly_widest_int::from (@var{value}, @var{sign}) 9148dd4bdcdSmrgConvert @var{value} to a @code{poly_widest_int}, extending its coefficients 9158dd4bdcdSmrgaccording to @var{sign} if they have fewer bits than @code{widest_int}. 9168dd4bdcdSmrg@end table 9178dd4bdcdSmrg 9188dd4bdcdSmrg@node Miscellaneous @code{poly_int} routines 9198dd4bdcdSmrg@section Miscellaneous @code{poly_int} routines 9208dd4bdcdSmrg 9218dd4bdcdSmrg@table @samp 9228dd4bdcdSmrg@item print_dec (@var{value}, @var{file}, @var{sign}) 9238dd4bdcdSmrg@itemx print_dec (@var{value}, @var{file}) 9248dd4bdcdSmrgPrint @var{value} to @var{file} as a decimal value, interpreting 9258dd4bdcdSmrgthe coefficients according to @var{sign}. The final argument is 9268dd4bdcdSmrgoptional if @var{value} has an inherent sign; for example, 9278dd4bdcdSmrg@code{poly_int64} values print as signed by default and 9288dd4bdcdSmrg@code{poly_uint64} values print as unsigned by default. 9298dd4bdcdSmrg 9308dd4bdcdSmrgThis is a simply a @code{poly_int} version of a wide-int routine. 9318dd4bdcdSmrg@end table 9328dd4bdcdSmrg 9338dd4bdcdSmrg@node Guidelines for using @code{poly_int} 9348dd4bdcdSmrg@section Guidelines for using @code{poly_int} 9358dd4bdcdSmrg 9368dd4bdcdSmrgOne of the main design goals of @code{poly_int} was to make it easy 9378dd4bdcdSmrgto write target-independent code that handles variable-sized registers 9388dd4bdcdSmrgeven when the current target has fixed-sized registers. There are two 9398dd4bdcdSmrgaspects to this: 9408dd4bdcdSmrg 9418dd4bdcdSmrg@itemize 9428dd4bdcdSmrg@item 9438dd4bdcdSmrgThe set of @code{poly_int} operations should be complete enough that 9448dd4bdcdSmrgthe question in most cases becomes ``Can we do this operation on these 9458dd4bdcdSmrgparticular @code{poly_int} values? If not, bail out'' rather than 9468dd4bdcdSmrg``Are these @code{poly_int} values constant? If so, do the operation, 9478dd4bdcdSmrgotherwise bail out''. 9488dd4bdcdSmrg 9498dd4bdcdSmrg@item 9508dd4bdcdSmrgIf target-independent code compiles and runs correctly on a target 9518dd4bdcdSmrgwith one value of @code{NUM_POLY_INT_COEFFS}, and if the code does not 9528dd4bdcdSmrguse asserting functions like @code{to_constant}, it is reasonable to 9538dd4bdcdSmrgassume that the code also works on targets with other values of 9548dd4bdcdSmrg@code{NUM_POLY_INT_COEFFS}. There is no need to check this during 9558dd4bdcdSmrgeveryday development. 9568dd4bdcdSmrg@end itemize 9578dd4bdcdSmrg 9588dd4bdcdSmrgSo the general principle is: if target-independent code is dealing 9598dd4bdcdSmrgwith a @code{poly_int} value, it is better to operate on it as a 9608dd4bdcdSmrg@code{poly_int} if at all possible, choosing conservatively-correct 9618dd4bdcdSmrgbehavior if a particular operation fails. For example, the following 9628dd4bdcdSmrgcode handles an index @code{pos} into a sequence of vectors that each 9638dd4bdcdSmrghave @code{nunits} elements: 9648dd4bdcdSmrg 9658dd4bdcdSmrg@smallexample 9668dd4bdcdSmrg/* Calculate which vector contains the result, and which lane of 9678dd4bdcdSmrg that vector we need. */ 9688dd4bdcdSmrgif (!can_div_trunc_p (pos, nunits, &vec_entry, &vec_index)) 9698dd4bdcdSmrg @{ 9708dd4bdcdSmrg if (dump_enabled_p ()) 9718dd4bdcdSmrg dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 9728dd4bdcdSmrg "Cannot determine which vector holds the" 9738dd4bdcdSmrg " final result.\n"); 9748dd4bdcdSmrg return false; 9758dd4bdcdSmrg @} 9768dd4bdcdSmrg@end smallexample 9778dd4bdcdSmrg 9788dd4bdcdSmrgHowever, there are some contexts in which operating on a 9798dd4bdcdSmrg@code{poly_int} is not possible or does not make sense. One example 9808dd4bdcdSmrgis when handling static initializers, since no current target supports 9818dd4bdcdSmrgthe concept of a variable-length static initializer. In these 9828dd4bdcdSmrgsituations, a reasonable fallback is: 9838dd4bdcdSmrg 9848dd4bdcdSmrg@smallexample 9858dd4bdcdSmrgif (@var{poly_value}.is_constant (&@var{const_value})) 9868dd4bdcdSmrg @{ 9878dd4bdcdSmrg @dots{} 9888dd4bdcdSmrg /* Operate on @var{const_value}. */ 9898dd4bdcdSmrg @dots{} 9908dd4bdcdSmrg @} 9918dd4bdcdSmrgelse 9928dd4bdcdSmrg @{ 9938dd4bdcdSmrg @dots{} 9948dd4bdcdSmrg /* Conservatively correct fallback. */ 9958dd4bdcdSmrg @dots{} 9968dd4bdcdSmrg @} 9978dd4bdcdSmrg@end smallexample 9988dd4bdcdSmrg 9998dd4bdcdSmrg@code{poly_int} also provides some asserting functions like 10008dd4bdcdSmrg@code{to_constant}. Please only use these functions if there is a 10018dd4bdcdSmrggood theoretical reason to believe that the assertion cannot fire. 10028dd4bdcdSmrgFor example, if some work is divided into an analysis phase and an 10038dd4bdcdSmrgimplementation phase, the analysis phase might reject inputs that are 10048dd4bdcdSmrgnot @code{is_constant}, in which case the implementation phase can 10058dd4bdcdSmrgreasonably use @code{to_constant} on the remaining inputs. The assertions 10068dd4bdcdSmrgshould not be used to discover whether a condition ever occurs ``in the 10078dd4bdcdSmrgfield''; in other words, they should not be used to restrict code to 10088dd4bdcdSmrgconstants at first, with the intention of only implementing a 10098dd4bdcdSmrg@code{poly_int} version if a user hits the assertion. 10108dd4bdcdSmrg 10118dd4bdcdSmrgIf a particular asserting function like @code{to_constant} is needed 10128dd4bdcdSmrgmore than once for the same reason, it is probably worth adding a 10138dd4bdcdSmrghelper function or macro for that situation, so that the justification 10148dd4bdcdSmrgonly needs to be given once. For example: 10158dd4bdcdSmrg 10168dd4bdcdSmrg@smallexample 10178dd4bdcdSmrg/* Return the size of an element in a vector of size SIZE, given that 10188dd4bdcdSmrg the vector has NELTS elements. The return value is in the same units 10198dd4bdcdSmrg as SIZE (either bits or bytes). 10208dd4bdcdSmrg 10218dd4bdcdSmrg to_constant () is safe in this situation because vector elements are 10228dd4bdcdSmrg always constant-sized scalars. */ 10238dd4bdcdSmrg#define vector_element_size(SIZE, NELTS) \ 10248dd4bdcdSmrg (exact_div (SIZE, NELTS).to_constant ()) 10258dd4bdcdSmrg@end smallexample 10268dd4bdcdSmrg 10278dd4bdcdSmrgTarget-specific code in @file{config/@var{cpu}} only needs to handle 10288dd4bdcdSmrgnon-constant @code{poly_int}s if @code{NUM_POLY_INT_COEFFS} is greater 10298dd4bdcdSmrgthan one. For other targets, @code{poly_int} degenerates to a compile-time 10308dd4bdcdSmrgconstant and is often interchangable with a normal scalar integer. 10318dd4bdcdSmrgThere are two main exceptions: 10328dd4bdcdSmrg 10338dd4bdcdSmrg@itemize 10348dd4bdcdSmrg@item 10358dd4bdcdSmrgSometimes an explicit cast to an integer type might be needed, such as to 10368dd4bdcdSmrgresolve ambiguities in a @code{?:} expression, or when passing values 10378dd4bdcdSmrgthrough @code{...} to things like print functions. 10388dd4bdcdSmrg 10398dd4bdcdSmrg@item 10408dd4bdcdSmrgTarget macros are included in target-independent code and so do not 10418dd4bdcdSmrghave access to the implicit conversion to a scalar integer. 10428dd4bdcdSmrgIf this becomes a problem for a particular target macro, the 10438dd4bdcdSmrgpossible solutions, in order of preference, are: 10448dd4bdcdSmrg 10458dd4bdcdSmrg@itemize 10468dd4bdcdSmrg@item 10478dd4bdcdSmrgConvert the target macro to a target hook (for all targets). 10488dd4bdcdSmrg 10498dd4bdcdSmrg@item 10508dd4bdcdSmrgPut the target's implementation of the target macro in its 10518dd4bdcdSmrg@file{@var{cpu}.c} file and call it from the target macro in the 10528dd4bdcdSmrg@file{@var{cpu}.h} file. 10538dd4bdcdSmrg 10548dd4bdcdSmrg@item 10558dd4bdcdSmrgAdd @code{to_constant ()} calls where necessary. The previous option 10568dd4bdcdSmrgis preferable because it will help with any future conversion of the 10578dd4bdcdSmrgmacro to a hook. 10588dd4bdcdSmrg@end itemize 10598dd4bdcdSmrg@end itemize 10608dd4bdcdSmrg 1061