From patchwork Wed Sep 6 20:18:24 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 111837 Delivered-To: patch@linaro.org Received: by 10.140.94.166 with SMTP id g35csp1461712qge; Wed, 6 Sep 2017 13:19:45 -0700 (PDT) X-Received: by 10.84.211.12 with SMTP id b12mr347709pli.365.1504729185805; Wed, 06 Sep 2017 13:19:45 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1504729185; cv=none; d=google.com; s=arc-20160816; b=oit7YCxboK6ZNLbUqKfTAYoluaJ6KEkVOHRxMXNwh8C2mJ1jVDmR4tpIDs0cfERnNT yTTbpWxLLf12b9AGBaLP1uGKjk3RIgvDTZWLbVSUV2dRpJ+ioUoolKGc1iW+rMivtF3s zyx5Z+1tXWc3QD0U9tmrQMPDTWzZ7OmcU99hiAp1Vca2fjf2nFQa+MGzg3km+PytKsWV 67MMg6mo7V0H/DhADd78BF4151sfSfXPZ8OimDmlal2KuMO1D/JCZsWj3gUBYy0ZLcUq Alf74n1QyaecklWt0lQ32ixB5A7/X2R/5jllS0NcC7XzfO5NJysFoIIl7PufsFjzrI3B th/w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=mime-version:user-agent:message-id:date:subject:mail-followup-to:to :from:delivered-to:sender:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=/AR/qPf7uMmLNiMuRs1VyUXb009pY69LLem2fnRT/JM=; b=Ck6/xBSwZMelgPqd/gVu85OgZfzMoi57erjmNjA0+h9gVlrxqw5ROmX06gfn9PBRNi M2QmyZ+PUdBFuuWwsuKLab1C/Pyk8RWd7xc6Z0X2QUxEGtLfdQ2B4I/TVnSbAL3kSTcf NmIrgkpPPwXyyJn5pwGk/m1TTfegYT2AhOnHejd6LUDk33qqRI4+wBTuz3otW8NwcD/S uxwXqh2j4NUM+Aj5rw7+BXCUy8G9EJqHs2F3lgXgSLVAvkwgU2JtPOGp+mqtHRW8VKpg 7rRL0E28ktW5hj2X647xQRuQnB42sKHFlrZRATSH8m5g2ipMqFyqDcsKfWfUQMp8FQfJ 1EYQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=RHgtq9BK; spf=pass (google.com: domain of gcc-patches-return-461644-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-461644-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id 33si480415plo.315.2017.09.06.13.19.42 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 06 Sep 2017 13:19:45 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-461644-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=RHgtq9BK; spf=pass (google.com: domain of gcc-patches-return-461644-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-461644-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; q=dns; s= default; b=WuNZ+WDgs/ymwfU50SiuP0mcuZ+pdqlDaowiZdLcggTWG9ralk9jW 97WgepDVoOv6708Ol5P+tG46119yX5NpaR8ynNBsYABAnamwdcR1Te01y7paQ4LR 1TNRD90+xn+ll0KUseVq5zOpqFFdefjyg5SZgtWxkiRq811azdvYjs= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; s= default; bh=tdyzrnNfWCcEU6kAzKAv7NUBb00=; b=RHgtq9BKwPw/JfmYLwqP d1rGyyX7Hyk460GcOo0pDmeB+g1KIn298Dr9yYZYjM7zkSS2CL9F+W+yzaKoOyK1 YhnuZLDMZ1fjvpBk3hAH2fKzek/zb+Aw8Hq3gL2jcsGGIol4X2GN8OGnZVoxTyWW cXhUZZ65GTEXWgrRr014ZXg= Received: (qmail 70785 invoked by alias); 6 Sep 2017 20:19:00 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 69811 invoked by uid 89); 6 Sep 2017 20:19:00 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-15.4 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-wr0-f170.google.com Received: from mail-wr0-f170.google.com (HELO mail-wr0-f170.google.com) (209.85.128.170) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 06 Sep 2017 20:18:38 +0000 Received: by mail-wr0-f170.google.com with SMTP id o42so5288718wrb.3 for ; Wed, 06 Sep 2017 13:18:37 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:mail-followup-to:subject:date:message-id :user-agent:mime-version; bh=W2klzBaLkozJRGnK7UA7BgO9pkr3yNjmmn56QNW63zU=; b=ozNx6RUZOXD5vcCHufWWEoYPL3t4WVPwzUtpSImtI48No0b8v472QhlhkfZ2ZiKPpt HxJ+849PUX1Cc9336j4YdiF25yLcdYw/JdeSvdBP/U63Eyvpif6Bp3oTAlaCQk4AfHyq 6uT79Hq3CFq6FOK38N+TBEQY+Ghd+S72X25WHf9Lbpa+omBze5K7Js2kt1Du3k+kCQ65 utFI2VWY8Hlnr+gtrM/jpQFNGYRDhfheqpvEgwNwfiA15Yr8oYXxrOarq5P2t/mCIY3Q sFOURzmMkOBiSasdjLLs3U5f/SlCEspMHw2wfCphHNeSZw9dTv7BVW1yeixiRE3TtCQ8 DEiw== X-Gm-Message-State: AHPjjUi55GONQxL2TU5ZALwEYhtOjXbiEJ3qa6SU5FF9VmA6GB9vjoAA Ox3G4EJo5xShYqaZyO3DNg== X-Google-Smtp-Source: ADKCNb7aFFYOCR/qJUXX00VSVLTYxLa3/fvHUnsnWDkNRKFSpIgQ9GDVsC6S5rNcSYjd6OZXueYQKQ== X-Received: by 10.223.152.199 with SMTP id w65mr240695wrb.254.1504729115291; Wed, 06 Sep 2017 13:18:35 -0700 (PDT) Received: from localhost ([95.145.139.63]) by smtp.gmail.com with ESMTPSA id e80sm1645651wmd.45.2017.09.06.13.18.26 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 06 Sep 2017 13:18:33 -0700 (PDT) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@linaro.org Subject: RFC: Representation of runtime offsets and sizes Date: Wed, 06 Sep 2017 21:18:24 +0100 Message-ID: <87mv678ttb.fsf@linaro.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux) MIME-Version: 1.0 The next main step in the SVE submission is to add support for offsets and sizes that are a runtime invariant rather than a compile time constant. This is an RFC about our approach for doing that. It's an update of https://gcc.gnu.org/ml/gcc/2016-11/msg00031.html (which covered more topics than this message). The size of an SVE register in bits can be any multiple of 128 between 128 and 2048 inclusive. The way we chose to represent this was to have a runtime indeterminate that counts the number of 128 bit blocks above the minimum of 128. If we call the indeterminate X then: * an SVE register has 128 + 128 * X bits (16 + 16 * X bytes) * the last int in an SVE vector is at byte offset 12 + 16 * X * etc. Although the maximum value of X is 15, we don't want to take advantage of that, since there's nothing particularly magical about the value. So we have two types of target: those for which there are no runtime indeterminates, and those for which there is one runtime indeterminate. We decided to generalise the interface slightly by allowing any number of indeterminates, although the underlying implementation is still limited to 0 and 1 for now. The main class for working with these runtime offsets and sizes is "poly_int". It represents a value of the form: C0 + C1 * X1 + ... + Cn * Xn where each coefficient Ci is a compile-time constant and where each indeterminate Xi is a nonnegative runtime value. The class takes two template parameters, one giving the number of coefficients and one giving the type of the coefficients. There are then typedefs for the common cases, with the number of coefficients being controlled by the target. poly_int is used for things like: - the number of elements in a VECTOR_TYPE - the size and number of units in a general machine_mode - the offset of something in the stack frame - SUBREG_BYTE - MEM_SIZE and MEM_OFFSET - mem_ref_offset (only a selective list). There are also rtx and tree representations of poly_int, although I've left those out of this RFC. The patch has detailed documentation -- which I've also attached as a PDF -- but the main points are: * there's no total ordering between poly_ints, so the best we can do when comparing them is to ask whether two values *might* or *must* be related in a particular way. E.g. if mode A has size 2 + 2X and mode B has size 4, the condition: GET_MODE_SIZE (A) <= GET_MODE_SIZE (B) is true for X<=1 and false for X>=2. This translates to: may_le (GET_MODE_SIZE (A), GET_MODE_SIZE (B)) == true must_le (GET_MODE_SIZE (A), GET_MODE_SIZE (B)) == false Of course, the may/must distinction already exists in things like alias analysis. * some poly_int arithmetic operations (notably division) are only possible for certain values. These operations therefore become conditional. * target-independent code is exposed to these restrictions even if the current target has no indeterminates. But: * we've tried to provide enough operations that poly_ints are easy to work with. * it means that developers working with non-SVE targets don't need to test SVE. If the code compiles on a non-SVE target, and if it doesn't use any asserting operations, it's reasonable to assume that it will work on SVE too. * for target-specific code, poly_int degenerates to a scalar if there are no runtime invariants for that target. Only very minor changes are needed to non-AArch64 targets. * poly_int operations should be (and in practice seem to be) as efficient as normal scalar operations on non-AArch64 targets. The patch really needs some self-tests (which weren't supported when we did the work originally), but otherwise it's what I'd like to submit. Thanks, Richard 10 Sizes and offsets as runtime invariants ****************************************** GCC allows the size of a hardware register to be a runtime invariant rather than a compile-time constant. This in turn means that various sizes and offsets must also be runtime invariants rather than compile-time constants, such as: * the size of a general 'machine_mode' (*note Machine Modes::); * the size of a spill slot; * the offset of something within a stack frame; * the number of elements in a vector; * the size and offset of a 'mem' rtx (*note Regs and Memory::); and * the byte offset in a 'subreg' rtx (*note Regs and Memory::). The motivating example is the Arm SVE ISA, whose vector registers can be any multiple of 128 bits between 128 and 2048 inclusive. The compiler normally produces code that works for all SVE register sizes, with the actual size only being known at runtime. GCC's main representation of such runtime invariants is the 'poly_int' class. This chapter describes what 'poly_int' does, lists the available operations, and gives some general usage guidelines. * Menu: * Overview of poly_int:: * Consequences of using poly_int:: * Comparisons involving poly_int:: * Arithmetic on poly_ints:: * Alignment of poly_ints:: * Computing bounds on poly_ints:: * Converting poly_ints:: * Miscellaneous poly_int routines:: * Guidelines for using poly_int:: ---- File: gccint.info, Node: Overview of poly_int, Next: Consequences of using poly_int, Up: poly_int 10.1 Overview of 'poly_int' =========================== We define indeterminates X1, ..., XN whose values are only known at runtime and use polynomials of the form: C0 + C1 * X1 + ... + CN * XN to represent a size or offset whose value might depend on some of these indeterminates. The coefficients C0, ..., CN are always known at compile time, with the C0 term being the "constant" part that does not depend on any runtime value. GCC uses the 'poly_int' class to represent these coefficients. The class has two template parameters: the first specifies the number of coefficients (N + 1) and the second specifies the type of the coefficients. For example, 'poly_int<2, unsigned short>' represents a polynomial with two coefficients (and thus one indeterminate), with each coefficient having type 'unsigned short'. When N is 0, the class degenerates to a single compile-time constant C0. The number of coefficients needed for compilation is a fixed property of each target and is specified by the configuration macro 'NUM_POLY_INT_COEFFS'. The default value is 1, since most targets do not have such runtime invariants. Targets that need a different value should '#define' the macro in their 'CPU-modes.def' file. *Note Back End::. 'poly_int' makes the simplifying requirement that each indeterminate must be a nonnegative integer. An indeterminate value of 0 should usually represent the minimum possible runtime value, with C0 specifying the value in that case. For example, when targetting the Arm SVE ISA, the single indeterminate represents the number of 128-bit blocks in a vector _beyond the minimum length of 128 bits_. Thus the number of 64-bit doublewords in a vector is 2 + 2 * X1. If an aggregate has a single SVE vector and 16 additional bytes, its total size is 32 + 16 * X1 bytes. The header file 'poly-int-types.h' provides typedefs for the most common forms of 'poly_int', all having 'NUM_POLY_INT_COEFFS' coefficients: 'poly_uint16' a 'poly_int' with 'unsigned short' coefficients. 'poly_int64' a 'poly_int' with 'HOST_WIDE_INT' coefficients. 'poly_uint64' a 'poly_int' with 'unsigned HOST_WIDE_INT' coefficients. 'poly_offset_int' a 'poly_int' with 'offset_int' coefficients. 'poly_wide_int' a 'poly_int' with 'wide_int' coefficients. 'poly_widest_int' a 'poly_int' with 'widest_int' coefficients. Since the main purpose of 'poly_int' is to represent sizes and offsets, the last two typedefs are only rarely used. ---- File: gccint.info, Node: Consequences of using poly_int, Next: Comparisons involving poly_int, Prev: Overview of poly_int, Up: poly_int 10.2 Consequences of using 'poly_int' ===================================== The two main consequences of using polynomial sizes and offsets are that: * there is no total ordering between the values at compile time, and * some operations might yield results that cannot be expressed as a 'poly_int'. For example, if X is a runtime invariant, we cannot tell at compile time whether: 3 + 4X <= 1 + 5X since the condition is false when X <= 1 and true when X >= 2. Similarly, 'poly_int' cannot represent the result of: (3 + 4X) * (1 + 5X) since it cannot (and in practice does not need to) store powers greater than one. It also cannot represent the result of: (3 + 4X) / (1 + 5X) The following sections describe how we deal with these restrictions. As described earlier, a 'poly_int<1, T>' has no indeterminates and so degenerates to a compile-constant of type T. It would be possible in that case to do all normal arithmetic on the T, and to compare the T using the normal C++ operators. We deliberately prevent target-independent code from doing this, since the compiler needs to support other 'poly_int' as well, regardless of the current target's 'NUM_POLY_INT_COEFFS'. However, it would be very artificial to force target-specific code to follow these restrictions if the target has no runtime indeterminates. There is therefore an implicit conversion from 'poly_int<1, T>' to T when compiling target-specific translation units. ---- File: gccint.info, Node: Comparisons involving poly_int, Next: Arithmetic on poly_ints, Prev: Consequences of using poly_int, Up: poly_int 10.3 Comparisons involving 'poly_int' ===================================== In general we need to compare sizes and offsets in two situations: those in which the values need to be ordered, and those in which the values can be unordered. More loosely, the distinction is often between values that have a definite link (usually because they refer to the same underlying register or memory location) and values that have no definite link. An example of the former is the relationship between the inner and outer sizes of a subreg, where we must know at compile time whether the subreg is paradoxical, partial, or complete. An example of the latter is alias analysis: we might want to check whether two arbitrary memory references overlap. Referring back to the examples in the previous section, it makes sense to ask whether a memory reference of size '3 + 4X' overlaps one of size '1 + 5X', but it does not make sense to have a subreg in which the outer mode has '3 + 4X' bytes and the inner mode has '1 + 5X' bytes (or vice versa). Such subregs are always invalid and should trigger an internal compiler error if formed. The underlying operators are the same in both cases, but the distinction affects how they are used. * Menu: * Comparison functions for poly_int:: * Properties of the poly_int comparisons:: * Comparing potentially-unordered poly_ints:: * Comparing ordered poly_ints:: * Checking for a poly_int marker value:: * Range checks on poly_ints:: * Sorting poly_ints:: ---- File: gccint.info, Node: Comparison functions for poly_int, Next: Properties of the poly_int comparisons, Up: Comparisons involving poly_int 10.3.1 Comparison functions for 'poly_int' ------------------------------------------ 'poly_int' provides the following routines for checking whether a particular relationship "may" (might) hold: may_lt may_le may_eq may_ge may_gt may_ne The functions have their natural meaning: 'may_lt(A, B)' Return true if A might be less than B. 'may_le(A, B)' Return true if A might be less than or equal to B. 'may_eq(A, B)' Return true if A might be equal to B. 'may_ne(A, B)' Return true if A might not be equal to B. 'may_ge(A, B)' Return true if A might be greater than or equal to B. 'may_gt(A, B)' Return true if A might be greater than B. For readability, 'poly_int' also provides "must" inverses of these functions: must_lt (A, B) == !may_ge (A, B) must_le (A, B) == !may_gt (A, B) must_eq (A, B) == !may_ne (A, B) must_ge (A, B) == !may_lt (A, B) must_gt (A, B) == !may_le (A, B) must_ne (A, B) == !may_eq (A, B) ---- File: gccint.info, Node: Properties of the poly_int comparisons, Next: Comparing potentially-unordered poly_ints, Prev: Comparison functions for poly_int, Up: Comparisons involving poly_int 10.3.2 Properties of the 'poly_int' comparisons ----------------------------------------------- All "may" relations except 'may_ne' are transitive, so for example: may_lt (A, B) && may_lt (B, C) implies may_lt (A, C) for all A, B and C. 'may_lt', 'may_gt' and 'may_ne' are irreflexive, so for example: !may_lt (A, A) is true for all A. 'may_le', 'may_eq' and 'may_ge' are reflexive, so for example: may_le (A, A) is true for all A. 'may_eq' and 'may_ne' are symmetric, so: may_eq (A, B) == may_eq (B, A) may_ne (A, B) == may_ne (B, A) for all A and B. In addition: may_le (A, B) == may_lt (A, B) || may_eq (A, B) may_ge (A, B) == may_gt (A, B) || may_eq (A, B) may_lt (A, B) == may_gt (B, A) may_le (A, B) == may_ge (B, A) However: may_le (A, B) && may_le (B, A) does not imply !may_ne (A, B) [== must_eq(A, B)] may_ge (A, B) && may_ge (B, A) does not imply !may_ne (A, B) [== must_eq(A, B)] One example is again 'A == 3 + 4X' and 'B == 1 + 5X', where 'may_le (A, B)', 'may_ge (A, B)' and 'may_ne (A, B)' all hold. 'may_le' and 'may_ge' are therefore not antisymetric and do not form a partial order. From the above, it follows that: * All "must" relations except 'must_ne' are transitive. * 'must_lt', 'must_ne' and 'must_gt' are irreflexive. * 'must_le', 'must_eq' and 'must_ge' are reflexive. Also: must_lt (A, B) == must_gt (B, A) must_le (A, B) == must_ge (B, A) must_lt (A, B) implies !must_lt (B, A) [asymmetry] must_gt (A, B) implies !must_gt (B, A) must_le (A, B) && must_le (B, A) == must_eq (A, B) [== !may_ne (A, B)] must_ge (A, B) && must_ge (B, A) == must_eq (A, B) [== !may_ne (A, B)] 'must_le' and 'must_ge' are therefore antisymmetric and are partial orders. However: must_le (A, B) does not imply must_lt (A, B) || must_eq (A, B) must_ge (A, B) does not imply must_gt (A, B) || must_eq (A, B) For example, 'must_le (4, 4 + 4X)' holds because the runtime indeterminate X is a nonnegative integer, but neither 'must_lt (4, 4 + 4X)' nor 'must_eq (4, 4 + 4X)' hold. ---- File: gccint.info, Node: Comparing potentially-unordered poly_ints, Next: Comparing ordered poly_ints, Prev: Properties of the poly_int comparisons, Up: Comparisons involving poly_int 10.3.3 Comparing potentially-unordered 'poly_int's -------------------------------------------------- In cases where there is no definite link between two 'poly_int's, we can usually make a conservatively-correct assumption. For example, the conservative assumption for alias analysis is that two references _might_ alias. One way of checking whether [BEGIN1, END1) might overlap [BEGIN2, END2) using the 'poly_int' comparisons is: may_gt (END1, BEGIN2) && may_gt (END2, BEGIN1) and another is: !(must_le (END1, BEGIN2) || must_le (END2, BEGIN1)) However, in this particular example, it is better to use the range helper functions instead. *Note Range checks on poly_ints::. ---- File: gccint.info, Node: Comparing ordered poly_ints, Next: Checking for a poly_int marker value, Prev: Comparing potentially-unordered poly_ints, Up: Comparisons involving poly_int 10.3.4 Comparing ordered 'poly_int's ------------------------------------ In cases where there is a definite link between two 'poly_int's, such as the outer and inner sizes of subregs, we usually require the sizes to be ordered by the 'must_le' partial order. 'poly_int' provides the following utility functions for ordered values: 'ordered_p (A, B)' Return true if A and B are ordered by the 'must_le' partial order. 'ordered_min (A, B)' Assert that A and B are ordered by 'must_le' and return the minimum of the two. When using this function, please add a comment explaining why the values are known to be ordered. 'ordered_max (A, B)' Assert that A and B are ordered by 'must_le' and return the maximum of the two. When using this function, please add a comment explaining why the values are known to be ordered. For example, if a subreg has an outer mode of size OUTER and an inner mode of size INNER: * the subreg is complete if must_eq (INNER, OUTER) * otherwise, the subreg is paradoxical if must_le (INNER, OUTER) * otherwise, the subreg is partial if must_le (OUTER, INNER) * otherwise, the subreg is ill-formed Thus the subreg is only valid if 'ordered_p (OUTER, INNER)' is true. If this condition is already known to be true then: * the subreg is complete if must_eq (INNER, OUTER) * the subreg is paradoxical if may_lt (INNER, OUTER) * the subreg is partial if may_lt (OUTER, INNER) with the three conditions being mutually-exclusive. Code that checks whether a subreg is valid would therefore generally check whether 'ordered_p' holds (in addition to whatever other checks are required for subreg validity). Code that is dealing with existing subregs can assert that 'ordered_p' holds and use either of the classifications above. ---- File: gccint.info, Node: Checking for a poly_int marker value, Next: Range checks on poly_ints, Prev: Comparing ordered poly_ints, Up: Comparisons involving poly_int 10.3.5 Checking for a 'poly_int' marker value --------------------------------------------- It is sometimes useful to have a special "marker value" that is not meant to be taken literally. For example, some code uses a size of -1 to represent an unknown size, rather than having to carry around a separate boolean to say whether the size is known. The best way of checking whether something is a marker value is 'must_eq'. Conversely the best way of checking whether something is _not_ a marker value is 'may_ne'. Thus in the size example just mentioned, 'must_eq (size, -1)' would check for an unknown size and 'may_ne (size, -1)' would check for a known size. ---- File: gccint.info, Node: Range checks on poly_ints, Next: Sorting poly_ints, Prev: Checking for a poly_int marker value, Up: Comparisons involving poly_int 10.3.6 Range checks on 'poly_int's ---------------------------------- As well as the core comparisons (*note Comparison functions for poly_int::), 'poly_int' provides utilities for various kinds of range check. In each case the range is represented by a start position and a length rather than a start position and an end position; this is because the former is used much more often than the latter in GCC. Also, the sizes can be -1 (or all ones for unsigned sizes) to indicate a range with a known start position but an unknown size. 'ranges_may_overlap_p (POS1, SIZE1, POS2, SIZE2)' Return true if the range described by POS1 and SIZE1 _might_ overlap the range described by POS2 and SIZE2. 'ranges_must_overlap_p (POS1, SIZE1, POS2, SIZE2)' Return true if the range described by POS1 and SIZE1 is known to overlap the range described by POS2 and SIZE2. 'known_subrange_p (POS1, SIZE1, POS2, SIZE2)' Return true if the range described by POS1 and SIZE1 is known to be contained in the range described by POS2 and SIZE2. 'maybe_in_range_p (VALUE, POS, SIZE)' Return true if VALUE _might_ be in the range described by POS and SIZE (in other words, return true if VALUE is not known to be outside that range). 'known_in_range_p (VALUE, POS, SIZE)' Return true if VALUE is known to be in the range described by POS and SIZE. ---- File: gccint.info, Node: Sorting poly_ints, Prev: Range checks on poly_ints, Up: Comparisons involving poly_int 10.3.7 Sorting 'poly_int's -------------------------- 'poly_int' provides the following routine for sorting: 'compare_sizes_for_sort (A, B)' Compare A and B in reverse lexicographical order (that is, compare the highest-indexed coefficients first). This can be useful when sorting data structures, since it has the effect of separating constant and non-constant values. If all values are nonnegative, the constant values come first. Note that the values do not necessarily end up in numerical order. For example, '1 + 1X' would come after '100' in the sort order, but may well be less than '100' at run time. ---- File: gccint.info, Node: Arithmetic on poly_ints, Next: Alignment of poly_ints, Prev: Comparisons involving poly_int, Up: poly_int 10.4 Arithmetic on 'poly_int's ============================== Addition, subtraction, negation and bit inversion all work normally for 'poly_int's. Multiplication by a constant multiplier and left shifting by a constant shift amount also work normally. General multiplication of two 'poly_int's is not supported and is not useful in practice. Other operations are only conditionally supported: the operation might succeed or might fail, depending on the inputs. This section describes both types of operation. * Menu: * Using poly_int with C++ arithmetic operators:: * wi arithmetic on poly_ints:: * Division of poly_ints:: * Other poly_int arithmetic:: ---- File: gccint.info, Node: Using poly_int with C++ arithmetic operators, Next: wi arithmetic on poly_ints, Up: Arithmetic on poly_ints 10.4.1 Using 'poly_int' with C++ arithmetic operators ----------------------------------------------------- The following C++ expressions are supported, where P1 and P2 are 'poly_int's and where C1 and C2 are scalars: -P1 ~P1 P1 + P2 P1 + C2 C1 + P2 P1 - P2 P1 - C2 C1 - P2 C1 * P2 P1 * C2 P1 << C2 P1 += P2 P1 += C2 P1 -= P2 P1 -= C2 P1 *= C2 P1 <<= C2 These arithmetic operations handle integer ranks in a similar way to C++. The main difference is that every coefficient narrower than 'HOST_WIDE_INT' promotes to 'HOST_WIDE_INT', whereas in C++ everything narrower than 'int' promotes to 'int'. For example: poly_uint16 + int -> poly_int64 unsigned int + poly_uint16 -> poly_int64 poly_int64 + int -> poly_int64 poly_int32 + poly_uint64 -> poly_uint64 uint64 + poly_int64 -> poly_uint64 poly_offset_int + int32 -> poly_offset_int offset_int + poly_uint16 -> poly_offset_int In the first two examples, both coefficients are narrower than 'HOST_WIDE_INT', so the result has coefficients of type 'HOST_WIDE_INT'. In the other examples, the coefficient with the highest rank "wins". If one of the operands is 'wide_int' or 'poly_wide_int', the rules are the same as for 'wide_int' arithmetic. ---- File: gccint.info, Node: wi arithmetic on poly_ints, Next: Division of poly_ints, Prev: Using poly_int with C++ arithmetic operators, Up: Arithmetic on poly_ints 10.4.2 'wi' arithmetic on 'poly_int's ------------------------------------- As well as the C++ operators, 'poly_int' supports the following overflow-checking 'wi' routines: wi::neg (P1, &OVERFLOW) wi::add (P1, P2, SIGN, &OVERFLOW) wi::sub (P1, P2, SIGN, &OVERFLOW) wi::mul (P1, C2, SIGN, &OVERFLOW) These routines just check whether overflow occurs on any individual coefficient; it is not possible to know at compile time whether the final runtime value would overflow. ---- File: gccint.info, Node: Division of poly_ints, Next: Other poly_int arithmetic, Prev: wi arithmetic on poly_ints, Up: Arithmetic on poly_ints 10.4.3 Division of 'poly_int's ------------------------------ Division of 'poly_int's is possible for certain inputs. The functions for division return true if the operation is possible and in most cases return the results by pointer. The routines are: 'multiple_p (A, B)' 'multiple_p (A, B, "IENT)' Return true if A is an exact multiple of B, storing the result in QUOTIENT if so. There are overloads for various combinations of polynomial and constant A, B and QUOTIENT. 'constant_multiple_p (A, B)' 'constant_multiple_p (A, B, "IENT)' Like 'multiple_p', but also test whether the multiple is a compile-time constant. 'can_div_trunc_p (A, B, "IENT)' 'can_div_trunc_p (A, B, "IENT, &REMAINDER)' Return true if we can calculate 'trunc (A / B)' at compile time, storing the result in QUOTIENT and REMAINDER if so. 'can_div_away_from_zero_p (A, B, "IENT)' Return true if we can calculate 'A / B' at compile time, rounding away from zero. Store the result in QUOTIENT if so. Note that this is true if and only if 'can_div_trunc_p' is true. The only difference is in the rounding of the result. There is also an asserting form of division: 'exact_div (A, B)' Assert that A is a multiple of B and return 'A / B'. The result is a 'poly_int' if A is a 'poly_int'. ---- File: gccint.info, Node: Other poly_int arithmetic, Prev: Division of poly_ints, Up: Arithmetic on poly_ints 10.4.4 Other 'poly_int' arithmetic ---------------------------------- There are tentative routines for other operations besides division: 'can_ior_p (A, B, &RESULT)' Return true if we can calculate 'A | B' at compile time, storing the result in RESULT if so. Also, ANDs with a value '(1 << Y) - 1' or its inverse can be treated as alignment operations. *Note Alignment of poly_ints::. In addition, the following miscellaneous routines are available: 'coeff_gcd (A)' Return the greatest common divisor of all nonzero coefficients in A, or zero if A is known to be zero. 'common_multiple (A, B)' Return a value that is a multiple of both A and B, where one value is a 'poly_int' and the other is a scalar. The result will be the least common multiple for some indeterminate values but not necessarily for all. 'force_common_multiple (A, B)' Return a value that is a multiple of both A and B, asserting that such a value exists. The result will be the least common multiple for some indeterminate values but not necessarily for all. When using this routine, please add a comment explaining why the assertion is known to hold. Please add any other operations that you find to be useful. ---- File: gccint.info, Node: Alignment of poly_ints, Next: Computing bounds on poly_ints, Prev: Arithmetic on poly_ints, Up: poly_int 10.5 Alignment of 'poly_int's ============================= 'poly_int' provides various routines for aligning values and for querying misalignments. In each case the alignment must be a power of 2. 'can_align_p (VALUE, ALIGN)' Return true if we can align VALUE up or down to the nearest multiple of ALIGN at compile time. The answer is the same for both directions. 'can_align_down (VALUE, ALIGN, &ALIGNED)' Return true if 'can_align_p'; if so, set ALIGNED to the greatest aligned value that is less than or equal to VALUE. 'can_align_up (VALUE, ALIGN, &ALIGNED)' Return true if 'can_align_p'; if so, set ALIGNED to the lowest aligned value that is greater than or equal to VALUE. 'known_equal_after_align_down (A, B, ALIGN)' Return true if we can align A and B down to the nearest ALIGN boundary at compile time and if the two results are equal. 'known_equal_after_align_up (A, B, ALIGN)' Return true if we can align A and B up to the nearest ALIGN boundary at compile time and if the two results are equal. 'aligned_lower_bound (VALUE, ALIGN)' Return a result that is no greater than VALUE and that is aligned to ALIGN. The result will the closest aligned value for some indeterminate values but not necessarily for all. For example, suppose we are allocating an object of SIZE bytes in a downward-growing stack whose current limit is given by LIMIT. If the object requires ALIGN bytes of alignment, the new stack limit is given by: aligned_lower_bound (LIMIT - SIZE, ALIGN) 'aligned_upper_bound (VALUE, ALIGN)' Likewise return a result that is no less than VALUE and that is aligned to ALIGN. This is the routine that would be used for upward-growing stacks in the scenario just described. 'known_misalignment (VALUE, ALIGN, &MISALIGN)' Return true if we can calculate the misalignment of VALUE with respect to ALIGN at compile time, storing the result in MISALIGN if so. 'known_alignment (VALUE)' Return the minimum alignment that VALUE is known to have (in other words, the largest alignment that can be guaranteed whatever the values of the indeterminates turn out to be). Return 0 if VALUE is known to be 0. 'force_align_down (VALUE, ALIGN)' Assert that VALUE can be aligned down to ALIGN at compile time and return the result. When using this routine, please add a comment explaining why the assertion is known to hold. 'force_align_up (VALUE, ALIGN)' Likewise, but aligning up. 'force_align_down_and_div (VALUE, ALIGN)' Divide the result of 'force_align_down' by ALIGN. Again, please add a comment explaining why the assertion in 'force_align_down' is known to hold. 'force_align_up_and_div (VALUE, ALIGN)' Likewise for 'force_align_up'. 'force_get_misalignment (VALUE, ALIGN)' Assert that we can calculate the misalignment of VALUE with respect to ALIGN at compile time and return the misalignment. When using this function, please add a comment explaining why the assertion is known to hold. ---- File: gccint.info, Node: Computing bounds on poly_ints, Next: Converting poly_ints, Prev: Alignment of poly_ints, Up: poly_int 10.6 Computing bounds on 'poly_int's ==================================== 'poly_int' also provides routines for calculating lower and upper bounds: 'constant_lower_bound (A)' Assert that A is nonnegative and return the smallest value it can have. 'lower_bound (A, B)' Return a value that is always less than or equal to both A and B. It will be the greatest such value for some indeterminate values but necessarily for all. 'upper_bound (A, B)' Return a value that is always greater than or equal to both A and B. It will be the least such value for some indeterminate values but necessarily for all. ---- File: gccint.info, Node: Converting poly_ints, Next: Miscellaneous poly_int routines, Prev: Computing bounds on poly_ints, Up: poly_int 10.7 Converting 'poly_int's =========================== A 'poly_int' can be constructed from up to N individual T coefficients, with the remaining coefficients being implicitly zero. In particular, this means that every 'poly_int' can be constructed from a single scalar T, or someting compatible with T. Also, a 'poly_int' can be constructed from a 'poly_int' if T can be constructed from U. The following functions provide other forms of conversion, or test whether such a conversion would succeed. 'VALUE.is_constant ()' Return true if 'poly_int' VALUE is a compile-time constant. 'VALUE.is_constant (&C1)' Return true if 'poly_int' VALUE is a compile-time constant, storing it in C1 if so. C1 must be able to hold all constant values of VALUE without loss of precision. 'VALUE.to_constant ()' Assert that VALUE is a compile-time constant and return its value. When using this function, please add a comment explaining why the condition is known to hold (for example, because an earlier phase of analysis rejected non-constants). 'VALUE.to_shwi (&P2)' Return true if 'poly_int' VALUE can be represented without loss of precision as a 'poly_int', storing it in that form in P2 if so. 'VALUE.to_uhwi (&P2)' Return true if 'poly_int' VALUE can be represented without loss of precision as a 'poly_int', storing it in that form in P2 if so. 'VALUE.force_shwi ()' Forcibly convert each coefficient of 'poly_int' VALUE to 'HOST_WIDE_INT', truncating any that are out of range. Return the result as a 'poly_int'. 'VALUE.force_uhwi ()' Forcibly convert each coefficient of 'poly_int' VALUE to 'unsigned HOST_WIDE_INT', truncating any that are out of range. Return the result as a 'poly_int'. 'wi::sext (VALUE, PRECISION)' Return a 'poly_int' of the same type as VALUE, sign-extending every coefficient from the low PRECISION bits. This in effect applies 'wi::sext' to each coefficient individually. 'poly_wide_int::from (VALUE, PRECISION, SIGN)' Convert VALUE to a 'poly_wide_int' in which each coefficient has PRECISION bits. Extend the coefficients according to SIGN if the coefficients have fewer bits. 'poly_offset_int::from (VALUE, SIGN)' Convert VALUE to a 'poly_offset_int', extending its coefficients according to SIGN if they have fewer bits than 'offset_int'. 'poly_widest_int::from (VALUE, SIGN)' Convert VALUE to a 'poly_widest_int', extending its coefficients according to SIGN if they have fewer bits than 'widest_int'. ---- File: gccint.info, Node: Miscellaneous poly_int routines, Next: Guidelines for using poly_int, Prev: Converting poly_ints, Up: poly_int 10.8 Miscellaneous 'poly_int' routines ====================================== 'print_dec (VALUE, FILE, SIGN)' Print VALUE to FILE as a decimal value, interpreting the coefficients according to SIGN. This is a simply a 'poly_int' version of a wide-int routine. ---- File: gccint.info, Node: Guidelines for using poly_int, Prev: Miscellaneous poly_int routines, Up: poly_int 10.9 Guidelines for using 'poly_int' ==================================== One of the main design goals of 'poly_int' was to make it easy to write target-independent code that handles variable-sized registers even when the current target has fixed-sized registers. There are two aspects to this: * The set of 'poly_int' operations should be complete enough that the question in most cases becomes "Can we do this operation on these particular 'poly_int' values? If not, bail out" rather than "Are these 'poly_int' values constant? If so, do the operation, otherwise bail out". * If target-independent code compiles and runs correctly on a target with one value of 'NUM_POLY_INT_COEFFS', and if the code does not use asserting functions like 'to_constant', it is reasonable to assume that the code also works on targets with other values of 'NUM_POLY_INT_COEFFS'. There is no need to check this during everyday development. So the general principle is: if target-independent code is dealing with a 'poly_int' value, it is better to operate on it as a 'poly_int' if at all possible, choosing conservatively-correct behavior if a particular operation fails. For example, the following code handles an index 'pos' into a sequence of vectors that each have 'nunits' elements: /* Calculate which vector contains the result, and which lane of that vector we need. */ if (!can_div_trunc_p (pos, nunits, &vec_entry, &vec_index)) { if (dump_enabled_p ()) dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, "Cannot determine which vector holds the" " final result.\n"); return false; } However, there are some contexts in which operating on a 'poly_int' is not possible or does not make sense. One example is when handling static initializers, since no current target supports the concept of a variable-length static initializer. In these situations, a reasonable fallback is: if (POLY_VALUE.is_constant (&CONST_VALUE)) { ... /* Operate on CONST_VALUE. */ ... } else { ... /* Conservatively correct fallback. */ ... } 'poly_int' also provides some asserting functions like 'to_constant'. Please only use these functions if there is a good theoretical reason to believe that the assertion cannot fire. For example if some work is divided into an analysis phase and an implementation phase, the analysis phase might reject inputs that are not 'is_constant', in which case the implementation phase can reasonably use 'to_constant' on the remaining inputs. The assertions should not be used to discover whether a condition ever occurs "in the field"; in other words, they should not be used to restrict code to constants at first, with the intention of only implementing a 'poly_int' version if a user hits the assertion. If a particular asserting function like 'to_constant' is needed more than once for the same reason, it is probably worth adding a helper function or macro for that situation, so that the justification only needs to be given once. For example: /* Return the size of an element in a vector of size SIZE, given that the vector has NELTS elements. The return value is in the same units as SIZE (either bits or bytes). to_constant () is safe in this situation because vector elements are always constant-sized scalars. */ #define vector_element_size(SIZE, NELTS) \ (exact_div (SIZE, NELTS).to_constant ()) Target-specific code in 'config/CPU' only needs to handle non-constant 'poly_int's if 'NUM_POLY_INT_COEFFS' is greater than one. For other targets, 'poly_int' degenerates to a compile-time constant and is often interchangable with a normal salar integer. There are two main exceptions: * Sometimes an explicit cast to an integer type might be needed, such as to resolve ambiguities in a '?:' expression, or when passing values through '...' to things like print functions. * Target macros are included in target-independent code and so do not have access to the implicit conversion to a scalar integer. If this becomes a problem for a particular target macro, the possible solutions, in order of preference, are: * Convert the target macro to a target hook (for all targets). * Put the target's implementation of the target macro in its 'CPU.c' file and call it from the target macro in the 'CPU.h' file. * Add 'to_constant ()' calls where necessary. The previous option is preferable because it will help with any future conversion of the macro to a hook. 2017-09-06 Richard Sandiford Alan Hayward David Sherwood gcc/ * poly-int.h: New file. * poly-int-types.h: Likewise. * coretypes.h: Include them. (POLY_INT_CONVERSION): Define. * target.def (estimated_poly_value): New hook. * doc/tm.texi.in (TARGET_ESTIMATED_POLY_VALUE): New hook. * doc/tm.texi: Regenerate. * doc/poly-int.texi: New file. * doc/gccint.texi: Include it. * Makefile.in (TEXI_GCCINT_FILES): Add poly-int.texi. * genmodes.c (NUM_POLY_INT_COEFFS): Provide default definition. (emit_insn_modes_h): Emit a definition of NUM_POLY_INT_COEFFS. * targhooks.h (default_estimated_poly_value): Declare. * targhooks.c (default_estimated_poly_value): New function. * target.h (estimated_poly_value): Likewise. * wide-int.h (WI_UNARY_RESULT): Use wi::binary_traits. (wi::unary_traits): Delete. (operator /): New function. (operator %): Likewise. Index: gcc/poly-int.h =================================================================== --- /dev/null 2017-09-06 19:36:35.113864212 +0100 +++ gcc/poly-int.h 2017-09-06 20:51:42.952931683 +0100 @@ -0,0 +1,2011 @@ +/* Polynomial integer classes. + Copyright (C) 2014-2017 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +/* This file provides a representation of sizes and offsets whose exact + values depend on certain runtime properties. The motivating example + is the Arm SVE ISA, in which the number of vector elements is only + known at runtime. See doc/poly-int.texi for more details. */ + +#ifndef HAVE_POLY_INT_H +#define HAVE_POLY_INT_H + +/* int_traits::rank is less than int_traits::rank if T1 can + promote to T2. + + For C-like types the rank is: + + (2 * number of bytes) + (unsigned ? 1 : 0) + + wide_ints don't have a normal rank and so use a value of INT_MAX. + Any fixed-width integer should be promoted to wide_int if possible + and lead to an error otherwise. + + int_traits::precision is the number of bits that T can hold. + + int_traits::signedness is: + 0 if T1 is unsigned + 1 if T1 is signed + -1 if T1 has no inherent sign (as for wide_int). + + int_traits::result is a type that can hold results of operations + on T. This is different from T itself in cases where T is the result + of an accessor like wi::to_offset. */ +template::precision_type> +struct int_traits; + +template +struct int_traits +{ + typedef T result; + static const int signedness = (T (0) >= T (-1)); + static const int precision = sizeof (T) * CHAR_BIT; + static const int rank = sizeof (T) * 2 + !signedness; +}; + +template +struct int_traits +{ + typedef T result; + static const int signedness = -1; + static const int precision = WIDE_INT_MAX_PRECISION; + static const int rank = INT_MAX; +}; + +template +struct int_traits +{ + typedef WI_UNARY_RESULT (T) result; + static const int signedness = 1; + static const int precision = wi::int_traits::precision; + /* These types are always signed. */ + static const int rank = precision * 2 / CHAR_BIT; +}; + +/* SFINAE class that leads to substitution failure if T2 can't represent + all the values in T1. Either: + + - T2 should be a type with the same signedness as T1 and no less precision. + This allows things like int16_t -> int16_t and uint32_t -> uint64_t. + + - T1 should be unsigned, T2 should be signed, and T1 should be + narrower than T2. This allows things like uint16_t -> int32_t. + + This rules out cases in which T2 has less precision than T1 or where + the conversion would reinterpret the top bit. E.g. int16_t -> uint32_t + can be dangerous and should have an explicit cast if deliberate. */ +template::signedness + == int_traits::signedness + ? (int_traits::precision + <= int_traits::precision) + : (int_traits::signedness == 0 + && int_traits::signedness == 1 + && (int_traits::precision + < int_traits::precision)))> +struct if_lossless; + +template +struct if_lossless +{ + typedef bool bool_type; +}; + +/* A base POD class for polynomial integers. The polynomial has N + coefficients of type C. + + Most of these functions are ALWAYS_INLINE to speed up compilers + built at -O0. The functions are heavily used and not interesting + as function calls even in debug builds. */ +template +class poly_int_pod +{ +public: + typedef C t; + + template + poly_int_pod &operator = (const poly_int_pod &); + poly_int_pod &operator = (const C &); + + template + poly_int_pod &operator += (const poly_int_pod &); + poly_int_pod &operator += (const C &); + + template + poly_int_pod &operator -= (const poly_int_pod &); + poly_int_pod &operator -= (const C &); + + poly_int_pod &operator *= (const C &); + + poly_int_pod &operator <<= (unsigned int); + + bool is_constant () const; + + template + typename if_lossless::bool_type is_constant (T *) const; + + C to_constant () const; + + template + static poly_int_pod from (const poly_int_pod &, + unsigned int, signop); + template + static poly_int_pod from (const poly_int_pod &, signop); + bool to_shwi (poly_int_pod *) const; + bool to_uhwi (poly_int_pod *) const; + poly_int_pod force_shwi () const; + poly_int_pod force_uhwi () const; + +#if POLY_INT_CONVERSION + operator C () const; +#endif + + C coeffs[N]; +}; + +template +template +ALWAYS_INLINE poly_int_pod& +poly_int_pod::operator = (const poly_int_pod &a) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] = a.coeffs[0]; + if (N == 2) + this->coeffs[1] = a.coeffs[1]; + return *this; +} + +template +ALWAYS_INLINE poly_int_pod& +poly_int_pod::operator = (const C &a) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] = a; + if (N == 2) + /* Easy way of propagating the precision of a wide_int to the + second coefficient. */ + this->coeffs[1] = this->coeffs[0] & 0; + return *this; +} + +template +template +ALWAYS_INLINE poly_int_pod& +poly_int_pod::operator += (const poly_int_pod &a) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] += a.coeffs[0]; + if (N == 2) + this->coeffs[1] += a.coeffs[1]; + return *this; +} + +template +ALWAYS_INLINE poly_int_pod& +poly_int_pod::operator += (const C &a) +{ + this->coeffs[0] += a; + return *this; +} + +template +template +ALWAYS_INLINE poly_int_pod& +poly_int_pod::operator -= (const poly_int_pod &a) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] -= a.coeffs[0]; + if (N == 2) + this->coeffs[1] -= a.coeffs[1]; + return *this; +} + +template +ALWAYS_INLINE poly_int_pod& +poly_int_pod::operator -= (const C &a) +{ + this->coeffs[0] -= a; + return *this; +} + +template +ALWAYS_INLINE poly_int_pod& +poly_int_pod::operator *= (const C &a) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] *= a; + if (N == 2) + this->coeffs[1] *= a; + return *this; +} + +template +ALWAYS_INLINE poly_int_pod& +poly_int_pod::operator <<= (unsigned int a) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] = wi::lshift (this->coeffs[0], a); + if (N == 2) + this->coeffs[1] = wi::lshift (this->coeffs[1], a); + return *this; +} + +/* Return true if the polynomial value is a compile-time constant. */ + +template +ALWAYS_INLINE bool +poly_int_pod::is_constant () const +{ + STATIC_ASSERT (N <= 2); + return N == 1 || this->coeffs[1] == 0; +} + +/* Return true if the polynomial value is a compile-time constant, + storing its value in CONST_VALUE if so. */ + +template +template +ALWAYS_INLINE typename if_lossless::bool_type +poly_int_pod::is_constant (T *const_value) const +{ + if (is_constant ()) + { + *const_value = this->coeffs[0]; + return true; + } + return false; +} + +/* Return the value of a polynomial that is already known to be a + compile-time constant. + + NOTE: When using this function, please add a comment above the call + explaining why we know the value is constant in that context. */ + +template +ALWAYS_INLINE C +poly_int_pod::to_constant () const +{ + gcc_checking_assert (is_constant ()); + return this->coeffs[0]; +} + +/* Convert X to a wide-int-based polynomial in which each coefficient + has BITSIZE bits. If X's coefficients are smaller than BITSIZE, + extend them according to SGN. */ + +template +template +inline poly_int_pod +poly_int_pod::from (const poly_int_pod &a, + unsigned int bitsize, signop sgn) +{ + poly_int_pod r; + for (unsigned int i = 0; i < N; i++) + r.coeffs[i] = C::from (a.coeffs[i], bitsize, sgn); + return r; +} + +/* Convert X to a fixed-wide-int-based polynomial, extending according + to SGN. */ + +template +template +inline poly_int_pod +poly_int_pod::from (const poly_int_pod &a, signop sgn) +{ + poly_int_pod r; + for (unsigned int i = 0; i < N; i++) + r.coeffs[i] = C::from (a.coeffs[i], sgn); + return r; +} + +/* Return true if the coefficients of this wide-int-based polynomial can + be represented as signed HOST_WIDE_INTs without loss of precision. + Store the HOST_WIDE_INT representation in *R if so. */ + +template +inline bool +poly_int_pod::to_shwi (poly_int_pod *r) const +{ + for (unsigned int i = 0; i < N; i++) + if (!wi::fits_shwi_p (this->coeffs[i])) + return false; + for (unsigned int i = 0; i < N; i++) + r->coeffs[i] = this->coeffs[i].to_shwi (); + return true; +} + +/* Return true if the coefficients of this wide-int-based polynomial can + be represented as unsigned HOST_WIDE_INTs without loss of precision. + Store the unsigned HOST_WIDE_INT representation in *R if so. */ + +template +inline bool +poly_int_pod::to_uhwi (poly_int_pod *r) const +{ + for (unsigned int i = 0; i < N; i++) + if (!wi::fits_uhwi_p (this->coeffs[i])) + return false; + for (unsigned int i = 0; i < N; i++) + r->coeffs[i] = this->coeffs[i].to_uhwi (); + return true; +} + +/* Force a wide-int based constant to HOST_WIDE_INT precision, + truncating if necessary. */ + +template +poly_int_pod +poly_int_pod::force_shwi () const +{ + poly_int_pod r; + for (unsigned int i = 0; i < N; i++) + r.coeffs[i] = this->coeffs[i].to_shwi (); + return r; +} + +/* Force a wide-int based constant to unsigned HOST_WIDE_INT precision, + truncating if necessary. */ + +template +poly_int_pod +poly_int_pod::force_uhwi () const +{ + poly_int_pod r; + for (unsigned int i = 0; i < N; i++) + r.coeffs[i] = this->coeffs[i].to_uhwi (); + return r; +} + +#if POLY_INT_CONVERSION +/* Provide a conversion operator to constants. */ + +template +ALWAYS_INLINE +poly_int_pod::operator C () const +{ + gcc_checking_assert (this->is_constant ()); + return this->coeffs[0]; +} +#endif + +/* The main class for polynomial integers. The class provides + constructors that are necessarily missing from the POD base. */ +template +class poly_int : public poly_int_pod +{ +public: + ALWAYS_INLINE poly_int () {} + + template + poly_int (const poly_int &); + template + poly_int (const poly_int_pod &); + template + poly_int (const C0 &); + template + poly_int (const C0 &, const C1 &); + + template + poly_int &operator += (const poly_int_pod &); + poly_int &operator += (const C &); + + template + poly_int &operator -= (const poly_int_pod &); + poly_int &operator -= (const C &); + + poly_int &operator *= (const C &); + + poly_int &operator <<= (unsigned int); +}; + +template +template +ALWAYS_INLINE +poly_int::poly_int (const poly_int &a) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] = a.coeffs[0]; + if (N == 2) + this->coeffs[1] = a.coeffs[1]; +} + +template +template +ALWAYS_INLINE +poly_int::poly_int (const poly_int_pod &a) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] = a.coeffs[0]; + if (N == 2) + this->coeffs[1] = a.coeffs[1]; +} + +template +template +ALWAYS_INLINE +poly_int::poly_int (const C0 &c0) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] = c0; + if (N == 2) + /* Easy way of propagating the precision of a wide_int to the + second coefficient. */ + this->coeffs[1] = this->coeffs[0] & 0; +} + +template +template +ALWAYS_INLINE +poly_int::poly_int (const C0 &c0, const C1 &c1) +{ + STATIC_ASSERT (N == 2); + this->coeffs[0] = c0; + this->coeffs[1] = c1; +} + +template +template +ALWAYS_INLINE poly_int& +poly_int::operator += (const poly_int_pod &a) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] += a.coeffs[0]; + if (N == 2) + this->coeffs[1] += a.coeffs[1]; + return *this; +} + +template +ALWAYS_INLINE poly_int& +poly_int::operator += (const C &a) +{ + this->coeffs[0] += a; + return *this; +} + +template +template +ALWAYS_INLINE poly_int& +poly_int::operator -= (const poly_int_pod &a) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] -= a.coeffs[0]; + if (N == 2) + this->coeffs[1] -= a.coeffs[1]; + return *this; +} + +template +ALWAYS_INLINE poly_int& +poly_int::operator -= (const C &a) +{ + this->coeffs[0] -= a; + return *this; +} + +template +ALWAYS_INLINE poly_int& +poly_int::operator *= (const C &a) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] *= a; + if (N == 2) + this->coeffs[1] *= a; + return *this; +} + +template +ALWAYS_INLINE poly_int& +poly_int::operator <<= (unsigned int a) +{ + STATIC_ASSERT (N <= 2); + this->coeffs[0] = wi::lshift (this->coeffs[0], a); + if (N == 2) + this->coeffs[1] = wi::lshift (this->coeffs[1], a); + return *this; +} + +/* SFINAE class to force T to be a non-polynomial arithmetic type. */ +template +struct if_nonpoly +{ + typedef bool bool_type; + typedef T t; +}; +template struct if_nonpoly > {}; +template struct if_nonpoly > {}; + +/* Likewise for two types T1 and T2. */ +template::t, + typename T4 = typename if_nonpoly::t> +struct if_nonpoly2 +{ + typedef bool bool_type; +}; + +/* SFINAE class to force T to be a polynomial type. */ +template struct if_poly {}; +template +struct if_poly > +{ + typedef bool bool_type; + typedef poly_int_pod t; +}; +template +struct if_poly > +{ + typedef bool bool_type; + typedef poly_int t; +}; + +/* poly_result::t gives the result type for T1 + T2. The intention + is to provide normal C-like rules for integer ranks, except that + everything smaller than HOST_WIDE_INT promotes to HOST_WIDE_INT. */ +#define RANK(X) int_traits::rank +template +struct poly_result; +#undef RANK + +/* Promote pair to HOST_WIDE_INT. */ +template +struct poly_result +{ + typedef poly_int t; +}; + +/* Promote pair to unsigned HOST_WIDE_INT. */ +template +struct poly_result +{ + typedef poly_int t; +}; + +/* Use normal wide-int rules. */ +template +struct poly_result +{ + typedef poly_int t; +}; + +#define POLY_POLY_RESULT(N, T1, T2) typename poly_result::t +#define POLY_SCALAR_RESULT(N, T1, T2) \ + typename poly_result::t>::t +#define SCALAR_POLY_RESULT(N, T1, T2) \ + typename poly_result::t, T2>::t + +template +ALWAYS_INLINE POLY_POLY_RESULT (N, Ca, Cb) +operator + (const poly_int_pod &a, const poly_int_pod &b) +{ + typedef POLY_POLY_RESULT (N, Ca, Cb)::t C; + STATIC_ASSERT (N <= 2); + poly_int r; + r.coeffs[0] = C (a.coeffs[0]) + b.coeffs[0]; + if (N == 2) + r.coeffs[1] = C (a.coeffs[1]) + b.coeffs[1]; + return r; +} + +template +ALWAYS_INLINE POLY_SCALAR_RESULT (N, Ca, Cb) +operator + (const poly_int_pod &a, const Cb &b) +{ + typedef POLY_SCALAR_RESULT (N, Ca, Cb)::t C; + STATIC_ASSERT (N <= 2); + poly_int r; + r.coeffs[0] = C (a.coeffs[0]) + b; + if (N == 2) + r.coeffs[1] = C (a.coeffs[1]); + return r; +} + +template +ALWAYS_INLINE SCALAR_POLY_RESULT (N, Ca, Cb) +operator + (const Ca &a, const poly_int_pod &b) +{ + typedef SCALAR_POLY_RESULT (N, Ca, Cb)::t C; + STATIC_ASSERT (N <= 2); + poly_int r; + r.coeffs[0] = C (a) + b.coeffs[0]; + if (N == 2) + r.coeffs[1] = C (b.coeffs[1]); + return r; +} + +namespace wi { +/* Poly version of wi::add, with the same interface. */ + +template +poly_int +add (const poly_int_pod &a, const poly_int_pod &b, + signop sgn, bool *overflow) +{ + poly_int_pod r; + *overflow = false; + bool suboverflow; + for (unsigned int i = 0; i < N; ++i) + { + r.coeffs[i] = wi::add (a.coeffs[i], b.coeffs[i], sgn, &suboverflow); + *overflow |= suboverflow; + } + return r; +} +} + +template +ALWAYS_INLINE POLY_POLY_RESULT (N, Ca, Cb) +operator - (const poly_int_pod &a, const poly_int_pod &b) +{ + typedef POLY_POLY_RESULT (N, Ca, Cb)::t C; + STATIC_ASSERT (N <= 2); + poly_int r; + r.coeffs[0] = C (a.coeffs[0]) - b.coeffs[0]; + if (N == 2) + r.coeffs[1] = C (a.coeffs[1]) - b.coeffs[1]; + return r; +} + +template +ALWAYS_INLINE POLY_SCALAR_RESULT (N, Ca, Cb) +operator - (const poly_int_pod &a, const Cb &b) +{ + typedef POLY_SCALAR_RESULT (N, Ca, Cb)::t C; + STATIC_ASSERT (N <= 2); + poly_int r; + r.coeffs[0] = C (a.coeffs[0]) - b; + if (N == 2) + r.coeffs[1] = C (a.coeffs[1]); + return r; +} + +template +ALWAYS_INLINE SCALAR_POLY_RESULT (N, Ca, Cb) +operator - (const Ca &a, const poly_int_pod &b) +{ + typedef SCALAR_POLY_RESULT (N, Ca, Cb)::t C; + STATIC_ASSERT (N <= 2); + poly_int r; + r.coeffs[0] = C (a) - b.coeffs[0]; + if (N == 2) + r.coeffs[1] = -C (b.coeffs[1]); + return r; +} + +namespace wi { +/* Poly version of wi::sub, with the same interface. */ + +template +poly_int +sub (const poly_int_pod &a, const poly_int_pod &b, + signop sgn, bool *overflow) +{ + poly_int r; + *overflow = false; + bool suboverflow; + for (unsigned int i = 0; i < N; ++i) + { + r.coeffs[i] = wi::sub (a.coeffs[i], b.coeffs[i], sgn, &suboverflow); + *overflow |= suboverflow; + } + return r; +} +} + +template +ALWAYS_INLINE POLY_POLY_RESULT (N, Ca, Ca) +operator - (const poly_int_pod &a) +{ + typedef POLY_POLY_RESULT (N, Ca, Ca)::t C; + poly_int r; + for (unsigned int i = 0; i < N; ++i) + r.coeffs[i] = -C (a.coeffs[i]); + return r; +} + +namespace wi { +/* Poly version of wi::neg, with the same interface. */ + +template +poly_int +neg (const poly_int_pod &a, bool *overflow) +{ + poly_int r; + *overflow = false; + bool suboverflow; + for (unsigned int i = 0; i < N; ++i) + { + r.coeffs[i] = wi::neg (a.coeffs[i], &suboverflow); + *overflow |= suboverflow; + } + return r; +} + +/* Poly version of wi::sext, with the same interface. */ + +template +inline POLY_POLY_RESULT (N, C, C) +sext (const poly_int_pod &a, unsigned int precision) +{ + POLY_POLY_RESULT (N, C, C) r; + for (unsigned int i = 0; i < N; ++i) + r.coeffs[i] = wi::sext (a.coeffs[i], precision); + return r; +} +} + +template +ALWAYS_INLINE POLY_SCALAR_RESULT (N, Ca, Cb) +operator * (const poly_int_pod &a, const Cb &b) +{ + typedef POLY_SCALAR_RESULT (N, Ca, Cb)::t C; + STATIC_ASSERT (N <= 2); + poly_int r; + r.coeffs[0] = C (a.coeffs[0]) * b; + if (N == 2) + r.coeffs[1] = C (a.coeffs[1]) * b; + return r; +} + +template +ALWAYS_INLINE SCALAR_POLY_RESULT (N, Ca, Cb) +operator * (const Ca &a, const poly_int_pod &b) +{ + typedef SCALAR_POLY_RESULT (N, Ca, Cb)::t C; + STATIC_ASSERT (N <= 2); + poly_int r; + r.coeffs[0] = C (a) * b.coeffs[0]; + if (N == 2) + r.coeffs[1] = C (a) * b.coeffs[1]; + return r; +} + +namespace wi { +/* Poly version of wi::mul, with the same interface. */ + +template +poly_int +mul (const poly_int_pod &a, const C &b, + signop sgn, bool *overflow) +{ + poly_int r; + *overflow = false; + bool suboverflow; + for (unsigned int i = 0; i < N; ++i) + { + r.coeffs[i] = wi::mul (a.coeffs[i], b, sgn, &suboverflow); + *overflow |= suboverflow; + } + return r; +} +} + +template +ALWAYS_INLINE POLY_POLY_RESULT (N, Ca, Ca) +operator << (const poly_int_pod &a, unsigned int b) +{ + typedef POLY_POLY_RESULT (N, Ca, Ca)::t C; + STATIC_ASSERT (N <= 2); + poly_int r; + r.coeffs[0] = wi::lshift (C (a.coeffs[0]), b); + if (N == 2) + r.coeffs[1] = wi::lshift (C (a.coeffs[1]), b); + return r; +} + +/* Return true if a0 + a1 * x might equal b0 + b1 * x for some nonnegative + integer x. */ + +template +inline bool +may_eq_2 (const Ca &a0, const Ca &a1, const Cb &b0, const Cb &b1) +{ + if (a1 != b1) + /* a0 + a1 * x == b0 + b1 * x + ==> (a1 - b1) * x == b0 - a0 + ==> x == (b0 - a0) / (a1 - b1) + + We need to test whether that's a valid value of x. + (b0 - a0) and (a1 - b1) must not have opposite signs + and the result must be integral. */ + return ((a1 < b1 ? b0 <= a0 : b0 >= a0) + && (b0 - a0) % (a1 - b1) == 0); + return a0 == b0; +} + +/* Return true if a0 + a1 * x might equal b for some nonnegative + integer x. */ + +template +inline bool +may_eq_2 (const Ca &a0, const Ca &a1, const Cb &b) +{ + if (a1 != 0) + /* a0 + a1 * x == b + ==> x == (b - a0) / a1 + + We need to test whether that's a valid value of x. + (b - a0) and a1 must not have opposite signs and the + result must be integral. For the latter test we use + "a0 - b" rather than "b - a0" in order to cope with + cases in which a0 is a wide_int. */ + return ((a1 < 0 ? b <= a0 : b >= a0) + && (a0 - b) % a1 == 0); + return a0 == b; +} + +/* Return true if A might equal B for some indeterminate values. */ + +template +ALWAYS_INLINE bool +may_eq (const poly_int_pod &a, const poly_int_pod &b) +{ + STATIC_ASSERT (N <= 2); + if (N == 2) + return may_eq_2 (a.coeffs[0], a.coeffs[1], b.coeffs[0], b.coeffs[1]); + return a.coeffs[0] == b.coeffs[0]; +} + +template +ALWAYS_INLINE typename if_nonpoly::bool_type +may_eq (const poly_int_pod &a, const Cb &b) +{ + STATIC_ASSERT (N <= 2); + if (N == 2) + return may_eq_2 (a.coeffs[0], a.coeffs[1], b); + return a.coeffs[0] == b; +} + +template +ALWAYS_INLINE typename if_nonpoly::bool_type +may_eq (const Ca &a, const poly_int_pod &b) +{ + STATIC_ASSERT (N <= 2); + if (N == 2) + return may_eq_2 (b.coeffs[0], b.coeffs[1], a); + return a == b.coeffs[0]; +} + +template +ALWAYS_INLINE typename if_nonpoly2::bool_type +may_eq (const Ca &a, const Cb &b) +{ + return a == b; +} + +/* Return true if A might not equal B for some indeterminate values. */ + +template +ALWAYS_INLINE bool +may_ne (const poly_int_pod &a, const poly_int_pod &b) +{ + STATIC_ASSERT (N <= 2); + if (N == 2 && a.coeffs[1] != b.coeffs[1]) + return true; + return a.coeffs[0] != b.coeffs[0]; +} + +template +ALWAYS_INLINE typename if_nonpoly::bool_type +may_ne (const poly_int_pod &a, const Cb &b) +{ + STATIC_ASSERT (N <= 2); + if (N == 2 && a.coeffs[1] != 0) + return true; + return a.coeffs[0] != b; +} + +template +ALWAYS_INLINE typename if_nonpoly::bool_type +may_ne (const Ca &a, const poly_int_pod &b) +{ + STATIC_ASSERT (N <= 2); + if (N == 2 && 0 != b.coeffs[1]) + return true; + return a != b.coeffs[0]; +} + +template +ALWAYS_INLINE typename if_nonpoly2::bool_type +may_ne (const Ca &a, const Cb &b) +{ + return a != b; +} + +/* Return true if A must be equal to B. */ +#define must_eq(A, B) (!may_ne (A, B)) + +/* Return true if A must be unequal to B. */ +#define must_ne(A, B) (!may_eq (A, B)) + +/* Return true if A might be less than or equal to B for some + indeterminate values. */ + +template +ALWAYS_INLINE bool +may_le (const poly_int_pod &a, const poly_int_pod &b) +{ + STATIC_ASSERT (N <= 2); + if (N == 2 && a.coeffs[1] < b.coeffs[1]) + return true; + return a.coeffs[0] <= b.coeffs[0]; +} + +template +ALWAYS_INLINE typename if_nonpoly::bool_type +may_le (const poly_int_pod &a, const Cb &b) +{ + STATIC_ASSERT (N <= 2); + if (N == 2 && a.coeffs[1] < 0) + return true; + return a.coeffs[0] <= b; +} + +template +ALWAYS_INLINE typename if_nonpoly::bool_type +may_le (const Ca &a, const poly_int_pod &b) +{ + STATIC_ASSERT (N <= 2); + if (N == 2 && 0 < b.coeffs[1]) + return true; + return a <= b.coeffs[0]; +} + +template +ALWAYS_INLINE typename if_nonpoly2::bool_type +may_le (const Ca &a, const Cb &b) +{ + return a <= b; +} + +/* Return true if A might be less than B for some indeterminate values. */ + +template +ALWAYS_INLINE bool +may_lt (const poly_int_pod &a, const poly_int_pod &b) +{ + STATIC_ASSERT (N <= 2); + if (N == 2 && a.coeffs[1] < b.coeffs[1]) + return true; + return a.coeffs[0] < b.coeffs[0]; +} + +template +ALWAYS_INLINE typename if_nonpoly::bool_type +may_lt (const poly_int_pod &a, const Cb &b) +{ + STATIC_ASSERT (N <= 2); + if (N == 2 && a.coeffs[1] < 0) + return true; + return a.coeffs[0] < b; +} + +template +ALWAYS_INLINE typename if_nonpoly::bool_type +may_lt (const Ca &a, const poly_int_pod &b) +{ + STATIC_ASSERT (N <= 2); + if (N == 2 && 0 < b.coeffs[1]) + return true; + return a < b.coeffs[0]; +} + +template +ALWAYS_INLINE typename if_nonpoly2::bool_type +may_lt (const Ca &a, const Cb &b) +{ + return a < b; +} + +/* Return true if A may be greater than or equal to B. */ +#define may_ge(A, B) may_le (B, A) + +/* Return true if A may be greater than B. */ +#define may_gt(A, B) may_lt (B, A) + +/* Return true if A must be less than or equal to B. */ +#define must_le(A, B) (!may_gt (A, B)) + +/* Return true if A must be less than B. */ +#define must_lt(A, B) (!may_ge (A, B)) + +/* Return true if A must be greater than B. */ +#define must_gt(A, B) (!may_le (A, B)) + +/* Return true if A must be greater than or equal to B. */ +#define must_ge(A, B) (!may_lt (A, B)) + +/* Return true if A and B are ordered by the partial ordering must_le. */ + +template +inline bool +ordered_p (const T1 &a, const T2 &b) +{ + return must_le (a, b) || must_le (b, a); +} + +/* Assert that A and B are known to be ordered and return the minimum + of the two. + + NOTE: When using this function, please add a comment above the call + explaining why we know the values are ordered in that context. */ + +template +inline POLY_POLY_RESULT (N, Ca, Cb) +ordered_min (const poly_int_pod &a, const poly_int_pod &b) +{ + if (must_le (a, b)) + return a; + else + { + gcc_checking_assert (must_le (b, a)); + return b; + } +} + +template +inline SCALAR_POLY_RESULT (N, Ca, Cb) +ordered_min (const Ca &a, const poly_int_pod &b) +{ + if (must_le (a, b)) + return a; + else + { + gcc_checking_assert (must_le (b, a)); + return b; + } +} + +template +inline POLY_SCALAR_RESULT (N, Ca, Cb) +ordered_min (const poly_int_pod &a, const Cb &b) +{ + if (must_le (a, b)) + return a; + else + { + gcc_checking_assert (must_le (b, a)); + return b; + } +} + +/* Assert that A and B are known to be ordered and return the maximum + of the two. + + NOTE: When using this function, please add a comment above the call + explaining why we know the values are ordered in that context. */ + +template +inline POLY_POLY_RESULT (N, Ca, Cb) +ordered_max (const poly_int_pod &a, const poly_int_pod &b) +{ + if (must_le (a, b)) + return b; + else + { + gcc_checking_assert (must_le (b, a)); + return a; + } +} + +template +inline SCALAR_POLY_RESULT (N, Ca, Cb) +ordered_max (const Ca &a, const poly_int_pod &b) +{ + if (must_le (a, b)) + return b; + else + { + gcc_checking_assert (must_le (b, a)); + return a; + } +} + +template +inline POLY_SCALAR_RESULT (N, Ca, Cb) +ordered_max (const poly_int_pod &a, const Cb &b) +{ + if (must_le (a, b)) + return b; + else + { + gcc_checking_assert (must_le (b, a)); + return a; + } +} + +/* Return a constant lower bound on the value of A, which is known + to be nonnegative. */ + +template +inline Ca +constant_lower_bound (const poly_int_pod &a) +{ + gcc_checking_assert (must_ge (a, Ca (0))); + return a.coeffs[0]; +} + +/* Return a value that is known to be no greater than A and B, both of + which are known to be nonnegative. This will be the greatest lower + bound for some indeterminate values but not necessarily for all. */ + +template +inline POLY_SCALAR_RESULT (N, Ca, Cb) +lower_bound (const poly_int_pod &a, const Cb &b) +{ + typedef POLY_SCALAR_RESULT (N, Ca, Cb)::t C; + gcc_checking_assert (must_ge (a, Ca (0))); + gcc_checking_assert (b >= Cb (0)); + poly_int r; + r.coeffs[0] = MIN (C (a.coeffs[0]), C (b)); + for (unsigned int i = 1; i < N; ++i) + r.coeffs[1] = C (a.coeffs[i]); + return r; +} + +template +inline SCALAR_POLY_RESULT (N, Ca, Cb) +lower_bound (const Ca &a, const poly_int_pod &b) +{ + return lower_bound (b, a); +} + +template +inline POLY_POLY_RESULT (N, Ca, Cb) +lower_bound (const poly_int_pod &a, const poly_int_pod &b) +{ + typedef POLY_POLY_RESULT (N, Ca, Cb)::t C; + gcc_checking_assert (must_ge (a, Ca (0))); + gcc_checking_assert (must_ge (b, Cb (0))); + poly_int r; + for (unsigned int i = 0; i < N; ++i) + r.coeffs[i] = MIN (C (a.coeffs[i]), C (b.coeffs[i])); + return r; +} + +/* Return a value that is known to be no less than A and B, both of + which are known to be nonnegative. This will be the least upper + bound for some indeterminate values but not necessarily for all. */ + +template +inline POLY_SCALAR_RESULT (N, Ca, Cb) +upper_bound (const poly_int_pod &a, const Cb &b) +{ + typedef POLY_SCALAR_RESULT (N, Ca, Cb)::t C; + gcc_checking_assert (must_ge (a, Ca (0))); + gcc_checking_assert (b >= Cb (0)); + poly_int r; + r.coeffs[0] = MAX (C (a.coeffs[0]), C (b)); + for (unsigned int i = 1; i < N; ++i) + r.coeffs[1] = C (a.coeffs[i]); + return r; +} + +template +inline SCALAR_POLY_RESULT (N, Ca, Cb) +upper_bound (const Ca &a, const poly_int_pod &b) +{ + return upper_bound (b, a); +} + +template +inline POLY_POLY_RESULT (N, Ca, Cb) +upper_bound (const poly_int_pod &a, const poly_int_pod &b) +{ + typedef POLY_POLY_RESULT (N, Ca, Cb)::t C; + gcc_checking_assert (must_ge (a, Ca (0))); + gcc_checking_assert (must_ge (b, Cb (0))); + poly_int r; + for (unsigned int i = 0; i < N; ++i) + r.coeffs[i] = MAX (C (a.coeffs[i]), C (b.coeffs[i])); + return r; +} + +/* Return the greatest common divisor of all nonzero coefficients, or zero + if all coefficients are zero. */ + +template +inline Ca +coeff_gcd (const poly_int_pod &a) +{ + /* Find the first nonzero coefficient, stopping at 0 whatever happens. */ + unsigned int i; + for (i = N - 1; i > 0; --i) + if (a.coeffs[i] != 0) + break; + Ca r = a.coeffs[i]; + for (unsigned int j = 0; j < i; ++j) + if (a.coeffs[j] != 0) + r = gcd (r, a.coeffs[j]); + return r; +} + +/* Return a value that is a multiple of both A and B. This will be the + least common multiple for some indeterminate values but necessarily + for all. */ + +template +POLY_SCALAR_RESULT (N, Ca, Cb) +common_multiple (const poly_int_pod &a, Cb b) +{ + Ca xgcd = coeff_gcd (a); + return a * (least_common_multiple (xgcd, b) / xgcd); +} + +template +inline SCALAR_POLY_RESULT (N, Ca, Cb) +common_multiple (const Ca &a, const poly_int_pod &b) +{ + return common_multiple (b, a); +} + +/* Return a value that is a multiple of both A and B, asserting that + such a value exists. The result will be the least common multiple + for some indeterminate values but necessarily for all. + + NOTE: When using this function, please add a comment above the call + explaining why we know the values have a common multiple (which might + for example be because we know A / B is rational). */ + +template +POLY_POLY_RESULT (N, Ca, Cb) +force_common_multiple (const poly_int_pod &a, + const poly_int_pod &b) +{ + STATIC_ASSERT (N <= 2); + + if (b.is_constant ()) + return common_multiple (a, b.coeffs[0]); + if (a.is_constant ()) + return common_multiple (a.coeffs[0], b); + + gcc_assert (N == 2); + typedef POLY_POLY_RESULT (N, Ca, Cb)::t C; + + C lcm = least_common_multiple (a.coeffs[1], b.coeffs[1]); + C amul = lcm / a.coeffs[1]; + C bmul = lcm / b.coeffs[1]; + gcc_checking_assert (a.coeffs[0] * amul == b.coeffs[0] * bmul); + + return a * amul; +} + +/* Compare A and B for sorting purposes, returning -1 if A should come + before B, 0 if A and B are identical, and 1 if A should come after B. + This is a lexicographical compare of the coefficients in reverse order. + + A consequence of this is that all constant sizes come before all + non-constant ones, regardless of magnitude (since a size is never + negative). This is what most callers want. For example, when laying + data out on the stack, it's better to keep all the constant-sized + data together so that it can be accessed as a constant offset from a + single base. */ + +template +inline int +compare_sizes_for_sort (const poly_int_pod &a, + const poly_int_pod &b) +{ + for (unsigned int i = N; i-- > 0; ) + if (a.coeffs[i] != b.coeffs[i]) + return a.coeffs[i] < b.coeffs[i] ? -1 : 1; + return 0; +} + +/* Return true if we can calculate VALUE & (ALIGN - 1) at compile time. */ + +template +inline bool +can_align_p (const poly_int_pod &value, Cb align) +{ + for (unsigned int i = 1; i < N; i++) + if ((value.coeffs[i] & (align - 1)) != 0) + return false; + return true; +} + +/* Return true if we can align VALUE up to the smallest multiple of + ALIGN that is >= VALUE. Store the aligned value in *ALIGNED if so. */ + +template +inline bool +can_align_up (const poly_int_pod &value, Cb align, + poly_int *aligned) +{ + if (!can_align_p (value, align)) + return false; + *aligned = value + (-value.coeffs[0] & (align - 1)); + return true; +} + +/* Return true if we can align VALUE down to the largest multiple of + ALIGN that is <= VALUE. Store the aligned value in *ALIGNED if so. */ + +template +inline bool +can_align_down (const poly_int_pod &value, Cb align, + poly_int *aligned) +{ + if (!can_align_p (value, align)) + return false; + *aligned = value - (value.coeffs[0] & (align - 1)); + return true; +} + +/* Return true if we can align A and B to the smallest multiples of + ALIGN that are >= A and B respectively, and if doing so gives the + same value. */ + +template +inline bool +known_equal_after_align_up (const poly_int_pod &a, + const poly_int_pod &b, + Cc align) +{ + poly_int aligned_a; + poly_int aligned_b; + return (can_align_up (a, align, &aligned_a) + && can_align_up (b, align, &aligned_b) + && must_eq (aligned_a, aligned_b)); +} + +/* Return true if we can align A and B to the largest multiples of + ALIGN that are <= A and B respectively, and if doing so gives the + same value. */ + +template +inline bool +known_equal_after_align_down (const poly_int_pod &a, + const poly_int_pod &b, + Cc align) +{ + poly_int aligned_a; + poly_int aligned_b; + return (can_align_down (a, align, &aligned_a) + && can_align_down (b, align, &aligned_b) + && must_eq (aligned_a, aligned_b)); +} + +/* Assert that we can align VALUE to ALIGN at compile time and return + the smallest multiple of ALIGN that is >= VALUE. + + NOTE: When using this function, please add a comment above the call + explaining why we know the non-constant coefficients must already + be a multiple of ALIGN. */ + +template +inline poly_int +force_align_up (const poly_int_pod &value, Cb align) +{ + gcc_checking_assert (can_align_p (value, align)); + return value + (-value.coeffs[0] & (align - 1)); +} + +/* Assert that we can align VALUE to ALIGN at compile time and return + the largest multiple of ALIGN that is <= VALUE. + + NOTE: When using this function, please add a comment above the call + explaining why we know the non-constant coefficients must already + be a multiple of ALIGN. */ + +template +inline poly_int +force_align_down (const poly_int_pod &value, Cb align) +{ + gcc_checking_assert (can_align_p (value, align)); + return value - (value.coeffs[0] & (align - 1)); +} + +/* Return a value <= VALUE that is a multiple of ALIGN. It will be the + greatest such value for some indeterminate values but not necessarily + for all. */ + +template +inline poly_int +aligned_lower_bound (const poly_int_pod &value, Cb align) +{ + gcc_checking_assert (ordered_p (value, Ca (0))); + poly_int r; + for (unsigned int i = 0; i < N; ++i) + r.coeffs[i] = value.coeffs[i] & -Ca (align); + return r; +} + +/* Return a value >= VALUE that is a multiple of ALIGN. It will be the + least such value for some indeterminate values but not necessarily + for all. */ + +template +inline poly_int +aligned_upper_bound (const poly_int_pod &value, Cb align) +{ + gcc_checking_assert (ordered_p (value, Ca (0))); + poly_int r; + for (unsigned int i = 0; i < N; ++i) + r.coeffs[i] = value.coeffs[i] + (-value.coeffs[i] & Ca (align - 1)); + return r; +} + +/* Assert that we can align VALUE to ALIGN at compile time. Align VALUE + down to the largest multiple of ALIGN that is <= VALUE, then divide by + ALIGN. + + NOTE: When using this function, please add a comment above the call + explaining why we know the non-constant coefficients must already + be a multiple of ALIGN. */ + +template +inline poly_int +force_align_down_and_div (const poly_int_pod &value, Cb align) +{ + gcc_checking_assert (can_align_p (value, align)); + poly_int r; + r.coeffs[0] = (value.coeffs[0] - (value.coeffs[0] & (align - 1))) / align; + for (unsigned int i = 1; i < N; ++i) + r.coeffs[i] = value.coeffs[i] / align; + return r; +} + +/* Assert that we can align VALUE to ALIGN at compile time. Align VALUE + up to the smallest multiple of ALIGN that is >= VALUE, then divide by + ALIGN. + + NOTE: When using this function, please add a comment above the call + explaining why we know the non-constant coefficients must already + be a multiple of ALIGN. */ + +template +inline poly_int +force_align_up_and_div (const poly_int_pod &value, Cb align) +{ + gcc_checking_assert (can_align_p (value, align)); + poly_int r; + r.coeffs[0] = (value.coeffs[0] + (-value.coeffs[0] & (align - 1))) / align; + for (unsigned int i = 1; i < N; ++i) + r.coeffs[i] = value.coeffs[i] / align; + return r; +} + +/* Return true if we know at compile time the difference between VALUE + and the equal or preceding multiple of ALIGN. Store the value in + *MISALIGN if so. */ + +template +inline bool +known_misalignment (const poly_int_pod &value, Cb align, Cm *misalign) +{ + gcc_checking_assert (align != 0); + if (!can_align_p (value, align)) + return false; + *misalign = value.coeffs[0] & (align - 1); + return true; +} + +/* Return X & (Y - 1), asserting that this value is known. Please add + an a comment above callers to this function to explain why the condition + is known to hold. */ + +template +inline Ca +force_get_misalignment (const poly_int_pod &a, Cb align) +{ + gcc_checking_assert (can_align_p (a, align)); + return a.coeffs[0] & (align - 1); +} + +/* Return the maximum alignment that A is known to have. Return 0 + if A is known to be zero. */ + +template +inline Ca +known_alignment (const poly_int_pod &a) +{ + Ca r = a.coeffs[0]; + for (unsigned int i = 1; i < N; ++i) + r |= a.coeffs[1]; + return r & -r; +} + +/* Return true if we can compute A | B at compile time, storing the + result in RES if so. */ + +template +inline typename if_nonpoly::bool_type +can_ior_p (const poly_int_pod &a, Cb b, Cr *result) +{ + STATIC_ASSERT (N <= 2); + /* Coefficient 1 must be a multiple of something greater than B. */ + if (N == 2 + && a.coeffs[1] != 0 + && (a.coeffs[1] & -a.coeffs[1]) < b) + return false; + *result = a; + result->coeffs[0] |= b; + return true; +} + +/* Return true if A is a constant multiple of B, storing the + multiple in *MULTIPLE if so. */ + +template +inline typename if_nonpoly::bool_type +constant_multiple_p (const poly_int_pod &a, Cb b, Cm *multiple) +{ + /* Do the modulus before the constant check, to catch divide by + zero errors. */ + if (a.coeffs[0] % b != 0 || !a.is_constant ()) + return false; + *multiple = a.coeffs[0] / b; + return true; +} + +template +inline typename if_nonpoly::bool_type +constant_multiple_p (Ca a, const poly_int_pod &b, Cm *multiple) +{ + /* Do the modulus before the constant check, to catch divide by + zero errors. */ + if (a % b.coeffs[0] != 0 || (a != 0 && !b.is_constant ())) + return false; + *multiple = a / b.coeffs[0]; + return true; +} + +template +inline bool +constant_multiple_p (const poly_int_pod &a, + const poly_int_pod &b, Cm *multiple) +{ + STATIC_ASSERT (N <= 2); + if (b.is_constant ()) + return constant_multiple_p (a, b.coeffs[0], multiple); + + gcc_assert (N == 2); + typedef POLY_POLY_RESULT (N, Ca, Cb)::t C; + + /* Do this first, to catch divide-by-zero errors. */ + if (a.coeffs[0] % b.coeffs[0] != 0 + || a.coeffs[1] % b.coeffs[1] != 0) + return false; + + C r = a.coeffs[1] / b.coeffs[1]; + if (a.coeffs[0] / b.coeffs[0] != r) + return false; + + *multiple = r; + return true; +} + +/* Return true if A is a multiple of B. */ + +template +inline typename if_nonpoly2::bool_type +multiple_p (Ca a, Cb b) +{ + return a % b != 0; +} + +/* Return true if A is a (polynomial) multiple of B. */ + +template +inline typename if_nonpoly::bool_type +multiple_p (const poly_int_pod &a, Cb b) +{ + for (unsigned int i = 0; i < N; ++i) + if (a.coeffs[i] % b != 0) + return false; + return true; +} + +/* Return true if B is a constant and A is a (constant) multiple of B. */ + +template +inline typename if_nonpoly::bool_type +multiple_p (Ca a, const poly_int_pod &b) +{ + /* Do the modulus before the constant check, to catch divide by + potential zeros. */ + return a % b.coeffs[0] == 0 && b.is_constant (); +} + +/* Return true if A is a (polynomial) multiple of B. This handles cases + where either B is constant or the multiple is constant. */ + +template +inline bool +multiple_p (const poly_int_pod &a, const poly_int_pod &b) +{ + if (b.is_constant ()) + return multiple_p (a, b.coeffs[0]); + Ca tmp; + return constant_multiple_p (a, b, &tmp); +} + +/* Return true if A is a (constant) multiple of B, storing the + multiple in *MULTIPLE if so. */ + +template +inline typename if_nonpoly2::bool_type +multiple_p (Ca a, Cb b, Cm *multiple) +{ + if (a % b != 0) + return false; + *multiple = a / b; + return true; +} + +/* Return true if A is a (polynomial) multiple of B, storing the + multiple in *MULTIPLE if so. */ + +template +inline typename if_nonpoly::bool_type +multiple_p (const poly_int_pod &a, Cb b, poly_int_pod *multiple) +{ + if (!multiple_p (a, b)) + return false; + for (unsigned int i = 0; i < N; ++i) + multiple->coeffs[i] = a.coeffs[i] / b; + return true; +} + +/* Return true if B is a constant and A is a (constant) multiple of B, + storing the multiple in *MULTIPLE if so. */ + +template +inline typename if_nonpoly::bool_type +multiple_p (Ca a, const poly_int_pod &b, Cm *multiple) +{ + /* Do the modulus before the constant check, to catch divide by + potential zeros. */ + if (a % b.coeffs[0] != 0 || !b.is_constant ()) + return false; + *multiple = a / b.coeffs[0]; + return true; +} + +/* Return true if A is a (polynomial) multiple of B, storing the + multiple in *MULTIPLE if so. This handles cases where either + B is constant or the multiple is constant. */ + +template +inline bool +multiple_p (const poly_int_pod &a, const poly_int_pod &b, + poly_int *multiple) +{ + if (b.is_constant ()) + return multiple_p (a, b.coeffs[0], multiple); + return constant_multiple_p (a, b, multiple); +} + +/* Return A / B, given that A is known to be a multiple of B. */ + +template +inline POLY_SCALAR_RESULT (N, Ca, Cb) +exact_div (const poly_int_pod &a, Cb b) +{ + typedef POLY_POLY_RESULT (N, Ca, Cb)::t C; + poly_int r; + for (unsigned int i = 0; i < N; ++i) + { + gcc_checking_assert (a.coeffs[i] % b == 0); + r.coeffs[i] = a.coeffs[i] / b; + } + return r; +} + +/* Return A / B, given that A is known to be a multiple of B. */ + +template +inline POLY_POLY_RESULT (N, Ca, Cb) +exact_div (const poly_int_pod &a, const poly_int_pod &b) +{ + STATIC_ASSERT (N <= 2); + if (b.is_constant ()) + return exact_div (a, b.coeffs[0]); + + gcc_assert (N == 2); + typedef POLY_POLY_RESULT (N, Ca, Cb)::t C; + + gcc_checking_assert (a.coeffs[0] % b.coeffs[0] == 0 + && a.coeffs[1] % b.coeffs[1] == 0); + + C r = C (a.coeffs[0]) / b.coeffs[0]; + gcc_checking_assert (a.coeffs[1] / b.coeffs[1] == r); + return r; +} + +/* Return true if there is some constant Q and polynomial r such that: + + (1) a = b * Q + r + (2) |b * Q| <= |a| + (3) |r| < |b| + + Store the value Q in *QUOTIENT if so. */ + +template +inline typename if_nonpoly2::bool_type +can_div_trunc_p (const poly_int_pod &a, Cb b, Cq *quotient) +{ + /* Do the division before the constant check, to catch divide by + zero errors. */ + Cq q = a.coeffs[0] / b; + if (!a.is_constant ()) + return false; + *quotient = q; + return true; +} + +template +inline typename if_nonpoly::bool_type +can_div_trunc_p (const poly_int_pod &a, + const poly_int_pod &b, + Cq *quotient) +{ + STATIC_ASSERT (N <= 2); + if (b.is_constant ()) + return can_div_trunc_p (a, b.coeffs[0], quotient); + + /* For simplicity we only handle A and B that are ordered wrt 0. This + means that both coefficients are >= 0 or both coefficients are <= 0. */ + if (!ordered_p (a, Ca (0)) || !ordered_p (b, Cb (0))) + return false; + + /* We can calculate Q from the case in which the indeterminate is zero. */ + typedef POLY_POLY_RESULT (N, Ca, Cb)::t C; + C q = a.coeffs[0] / b.coeffs[0]; + + /* Calculate b1 * Q. */ + C bq1 = b.coeffs[1] * q; + + /* Check that: + + (2) |b * Q| <= |a|. + + We already know that this is true when the indeterminate is zero, + and we also know that |b * Q| and |a| are linear, so it can only + be false if |b * Q| has a higher gradient than |a|. */ + C a1 = a.coeffs[1]; + if ((bq1 < 0 ? -bq1 : bq1) > (a1 < 0 ? -a1 : a1)) + return false; + + /* Calculate r1 from this Q. */ + C r1 = a1 - bq1; + + /* Check that: + + (3) |r| < |b| + + as above. Note that since that this holds when the indeterminate + is zero, it also holds if the gradients are the same. */ + C b1 = b.coeffs[1]; + if ((r1 < 0 ? -r1 : r1) > (b1 < 0 ? -b1 : b1)) + return false; + + *quotient = q; + return true; +} + +/* Likewise, but also store r in *REMAINDER. */ + +template +inline typename if_nonpoly::bool_type +can_div_trunc_p (const poly_int_pod &a, + const poly_int_pod &b, + Cq *quotient, Cr *remainder) +{ + if (!can_div_trunc_p (a, b, quotient)) + return false; + *remainder = a - *quotient * b; + return true; +} + +/* Return true if there is some polynomial q and constant R such that: + + (1) a = B * q + R + (2) |B * q| <= |a| + (3) |R| < |B| + + Store the value q in *QUOTIENT if so. */ + +template +inline typename if_nonpoly::bool_type +can_div_trunc_p (const poly_int_pod &a, Cb b, + poly_int_pod *quotient) +{ + /* The remainder must be constant. */ + for (unsigned int i = 1; i < N; ++i) + if (a.coeffs[i] % b != 0) + return false; + for (unsigned int i = 0; i < N; ++i) + quotient->coeffs[i] = a.coeffs[i] / b; + return true; +} + +/* Likewise, but also store R in *REMAINDER. */ + +template +inline typename if_nonpoly::bool_type +can_div_trunc_p (const poly_int_pod &a, Cb b, + poly_int_pod *quotient, Cr *remainder) +{ + if (!can_div_trunc_p (a, b, quotient)) + return false; + *remainder = a.coeffs[0] % b; + return true; +} + +/* Return true if there is some constant Q and polynomial r such that: + + (1) a = b * Q + r + (2) |a| <= |b * Q| + (3) |r| < |b| + + Store the value Q in *QUOTIENT if so. */ + +template +inline typename if_nonpoly::bool_type +can_div_away_from_zero_p (const poly_int_pod &a, + const poly_int_pod &b, + Cq *quotient) +{ + if (!can_div_trunc_p (a, b, quotient)) + return false; + if (may_ne (*quotient * b, a)) + *quotient += (*quotient < 0 ? -1 : 1); + return true; +} + +/* Use print_dec to print VALUE to FILE, where SGN is the sign + of the values. */ + +template +void +print_dec (const poly_int_pod &value, FILE *file, signop sgn) +{ + if (value.is_constant ()) + print_dec (value.coeffs[0], file, sgn); + else + { + fprintf (file, "["); + for (unsigned int i = 0; i < N; ++i) + { + print_dec (value.coeffs[i], file, sgn); + fputc (i == N - 1 ? ']' : ',', file); + } + } +} + +#undef POLY_SCALAR_RESULT +#undef SCALAR_POLY_RESULT +#undef POLY_POLY_RESULT + +/* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2) + might overlap. SIZE1 and/or SIZE2 can be the special value -1, in which + case the range is open-ended. */ + +template +static inline bool +ranges_may_overlap_p (const T1 &pos1, const T2 &size1, + const T3 &pos2, const T4 &size2) +{ + /* The checks are written this way so that we can cope with signed + offsets and unsigned sizes. The "+ (x - x)"s avoid warnings about + comparisons between signed and unsigned in that case. */ + if (may_ge (pos1, pos2) + && (must_eq (size2, (size2 - size2) - 1) + || may_lt (pos1 - pos2 + (size2 - size2), size2))) + return true; + if (may_ge (pos2, pos1) + && (must_eq (size1, (size1 - size1) - 1) + || may_lt (pos2 - pos1 + (size1 - size1), size1))) + return true; + + return false; +} + +/* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2) + are known to overlap. SIZE1 and/or SIZE2 can be the special value -1, + in which case the range is open-ended. */ + +template +static inline bool +ranges_must_overlap_p (const T1 &pos1, const T2 &size1, + const T3 &pos2, const T4 &size2) +{ + /* The checks are written this way so that we can cope with signed + offsets and unsigned sizes. The "+ (x - x)"s avoid warnings about + comparisons between signed and unsigned in that case. */ + if (may_ne (size2, (size2 - size2) - 1) + && must_ge (pos1, pos2) + && must_lt (pos1 - pos2 + (size2 - size2), size2)) + return true; + if (may_ne (size1, (size1 - size1) - 1) + && must_ge (pos2, pos1) + && must_lt (pos2 - pos1 + (size1 - size1), size1)) + return true; + + return false; +} + +/* Return true if range [POS1, POS1 + SIZE1) is known to be a subrange of + [POS2, POS2 + SIZE2). SIZE1 and/or SIZE2 can be the special value -1, + in which case the range is open-ended. */ + +template +static inline bool +known_subrange_p (const T1 &pos1, const T2 &size1, + const T3 &pos2, const T4 &size2) +{ + return (may_ne (size1, (size1 - size1) - 1) + && may_ne (size2, (size2 - size2) - 1) + && must_ge (pos1, pos2) + && must_le (pos1 - pos2 + size1 + (size2 - size2), size2)); +} + +/* Return true if range [POS, POS + SIZE) is known to include VAL. + SIZE can be the special value -1, in which case the range is + open-ended. */ + +template +static inline bool +known_in_range_p (const T1 &val, const T2 &pos, const T3 &size) +{ + return (may_ne (size, (size - size) - 1) + && must_ge (val, pos) + && must_lt (val - pos + (size - size), size)); +} + +/* Return true if range [POS, POS + SIZE) might include VAL. + SIZE can be the special value -1, in which case the range is + open-ended. */ + +template +static inline bool +maybe_in_range_p (const T1 &val, const T2 &pos, const T3 &size) +{ + return (must_eq (size, (size - size) - 1) + || (may_ge (val, pos) && may_lt (val, pos + size))); +} + +template +void +gt_ggc_mx (poly_int_pod *) +{ +} + +template +void +gt_pch_nx (poly_int_pod *) +{ +} + +template +void +gt_pch_nx (poly_int_pod *, void (*) (void *, void *), void *) +{ +} + +#endif Index: gcc/poly-int-types.h =================================================================== --- /dev/null 2017-09-06 19:36:35.113864212 +0100 +++ gcc/poly-int-types.h 2017-09-06 20:51:42.952931683 +0100 @@ -0,0 +1,53 @@ +/* Typedefs for polynomial integers used in GCC. + Copyright (C) 2016-2017 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef HAVE_POLY_INT_TYPES_H +#define HAVE_POLY_INT_TYPES_H + +typedef poly_int_pod poly_uint16_pod; +typedef poly_int_pod poly_int64_pod; +typedef poly_int_pod poly_uint64_pod; +typedef poly_int_pod poly_offset_int_pod; +typedef poly_int_pod poly_wide_int_pod; +typedef poly_int_pod poly_widest_int_pod; + +typedef poly_int poly_uint16; +typedef poly_int poly_int64; +typedef poly_int poly_uint64; +typedef poly_int poly_offset_int; +typedef poly_int poly_wide_int; +typedef poly_int poly_widest_int; + +/* Divide bit quantity X by BITS_PER_UNIT and round down (towards -Inf). + If X is a bit size, this gives the number of whole bytes spanned by X. + + This is safe because non-constant mode sizes must be a whole number + of bytes in size. */ +#define bits_to_bytes_round_down(X) force_align_down_and_div (X, BITS_PER_UNIT) + +/* Divide bit quantity X by BITS_PER_UNIT and round up (towards +Inf). + If X is a bit size, this gives the number of whole or partial bytes + spanned by X. + + This is safe because non-constant mode sizes must be a whole number + of bytes in size. */ +#define bits_to_bytes_round_up(X) force_align_up_and_div (X, BITS_PER_UNIT) + +#endif Index: gcc/coretypes.h =================================================================== --- gcc/coretypes.h 2017-09-04 11:50:24.563372530 +0100 +++ gcc/coretypes.h 2017-09-06 20:51:42.950082490 +0100 @@ -396,6 +396,21 @@ typedef unsigned char uchar; #include "signop.h" #include "wide-int.h" #include "wide-int-print.h" + +/* On targets that don't need polynomial offsets, target-specific code + should be able to treat poly_int like a normal constant, with a + conversion operator going from the former to the latter. We also + allow this for gencondmd.c for all targets, so that we can treat + machine_modes as enums without causing build failures. */ +#if (defined (TARGET_C_FILE) \ + && (defined (USE_ENUM_MODES) || NUM_POLY_INT_COEFFS == 1)) +#define POLY_INT_CONVERSION 1 +#else +#define POLY_INT_CONVERSION 0 +#endif + +#include "poly-int.h" +#include "poly-int-types.h" #include "insn-modes-inline.h" #include "machmode.h" #include "double-int.h" Index: gcc/target.def =================================================================== --- gcc/target.def 2017-09-05 20:57:40.745898121 +0100 +++ gcc/target.def 2017-09-06 20:51:42.953881414 +0100 @@ -3687,6 +3687,14 @@ candidate as a replacement for the if-co bool, (rtx_insn *seq, struct noce_if_info *if_info), default_noce_conversion_profitable_p) +DEFHOOK +(estimated_poly_value, + "Return an estimate of the runtime value of @var{val}, for use in\n\ +things like cost calculations or profiling frequencies. The default\n\ +implementation returns the lowest possible value of @var{val}.", + HOST_WIDE_INT, (poly_int64 val), + default_estimated_poly_value) + /* Permit speculative instructions in delay slots during delayed-branch scheduling. */ DEFHOOK Index: gcc/doc/tm.texi.in =================================================================== --- gcc/doc/tm.texi.in 2017-09-04 11:50:24.566073698 +0100 +++ gcc/doc/tm.texi.in 2017-09-06 20:51:42.951981952 +0100 @@ -4710,6 +4710,8 @@ Define this macro if a non-short-circuit @hook TARGET_NO_SPECULATION_IN_DELAY_SLOTS_P +@hook TARGET_ESTIMATED_POLY_VALUE + @node Scheduling @section Adjusting the Instruction Scheduler Index: gcc/doc/tm.texi =================================================================== --- gcc/doc/tm.texi 2017-09-05 20:57:40.745898121 +0100 +++ gcc/doc/tm.texi 2017-09-06 20:51:42.951981952 +0100 @@ -6683,6 +6683,12 @@ delay slot branches filled using the bas as the delay slot can hide a pipeline bubble. @end deftypefn +@deftypefn {Target Hook} HOST_WIDE_INT TARGET_ESTIMATED_POLY_VALUE (poly_int64 @var{val}) +Return an estimate of the runtime value of @var{val}, for use in +things like cost calculations or profiling frequencies. The default +implementation returns the lowest possible value of @var{val}. +@end deftypefn + @node Scheduling @section Adjusting the Instruction Scheduler Index: gcc/doc/poly-int.texi =================================================================== --- /dev/null 2017-09-06 19:36:35.113864212 +0100 +++ gcc/doc/poly-int.texi 2017-09-06 20:51:42.951032221 +0100 @@ -0,0 +1,960 @@ +@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. + +@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-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. + +@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 relationship ``may'' (might) hold: + +@example +may_lt may_le may_eq may_ge may_gt + may_ne +@end example + +The functions have their natural meaning: + +@table @samp +@item may_lt(@var{a}, @var{b}) +Return true if @var{a} might be less than @var{b}. + +@item may_le(@var{a}, @var{b}) +Return true if @var{a} might be less than or equal to @var{b}. + +@item may_eq(@var{a}, @var{b}) +Return true if @var{a} might be equal to @var{b}. + +@item may_ne(@var{a}, @var{b}) +Return true if @var{a} might not be equal to @var{b}. + +@item may_ge(@var{a}, @var{b}) +Return true if @var{a} might be greater than or equal to @var{b}. + +@item may_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 ``must'' inverses of these +functions: + +@example +must_lt (@var{a}, @var{b}) == !may_ge (@var{a}, @var{b}) +must_le (@var{a}, @var{b}) == !may_gt (@var{a}, @var{b}) +must_eq (@var{a}, @var{b}) == !may_ne (@var{a}, @var{b}) +must_ge (@var{a}, @var{b}) == !may_lt (@var{a}, @var{b}) +must_gt (@var{a}, @var{b}) == !may_le (@var{a}, @var{b}) +must_ne (@var{a}, @var{b}) == !may_eq (@var{a}, @var{b}) +@end example + +@node Properties of the @code{poly_int} comparisons +@subsection Properties of the @code{poly_int} comparisons + +All ``may'' relations except @code{may_ne} are transitive, so for example: + +@smallexample +may_lt (@var{a}, @var{b}) && may_lt (@var{b}, @var{c}) implies may_lt (@var{a}, @var{c}) +@end smallexample + +for all @var{a}, @var{b} and @var{c}. @code{may_lt}, @code{may_gt} +and @code{may_ne} are irreflexive, so for example: + +@smallexample +!may_lt (@var{a}, @var{a}) +@end smallexample + +is true for all @var{a}. @code{may_le}, @code{may_eq} and @code{may_ge} +are reflexive, so for example: + +@smallexample +may_le (@var{a}, @var{a}) +@end smallexample + +is true for all @var{a}. @code{may_eq} and @code{may_ne} are symmetric, so: + +@smallexample +may_eq (@var{a}, @var{b}) == may_eq (@var{b}, @var{a}) +may_ne (@var{a}, @var{b}) == may_ne (@var{b}, @var{a}) +@end smallexample + +for all @var{a} and @var{b}. In addition: + +@smallexample +may_le (@var{a}, @var{b}) == may_lt (@var{a}, @var{b}) || may_eq (@var{a}, @var{b}) +may_ge (@var{a}, @var{b}) == may_gt (@var{a}, @var{b}) || may_eq (@var{a}, @var{b}) +may_lt (@var{a}, @var{b}) == may_gt (@var{b}, @var{a}) +may_le (@var{a}, @var{b}) == may_ge (@var{b}, @var{a}) +@end smallexample + +However: + +@smallexample +may_le (@var{a}, @var{b}) && may_le (@var{b}, @var{a}) does not imply !may_ne (@var{a}, @var{b}) [== must_eq(@var{a}, @var{b})] +may_ge (@var{a}, @var{b}) && may_ge (@var{b}, @var{a}) does not imply !may_ne (@var{a}, @var{b}) [== must_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{may_le (@var{a}, @var{b})}, +@samp{may_ge (@var{a}, @var{b})} and @samp{may_ne (@var{a}, @var{b})} +all hold. @code{may_le} and @code{may_ge} are therefore not antisymetric +and do not form a partial order. + +From the above, it follows that: + +@itemize @bullet +@item +All ``must'' relations except @code{must_ne} are transitive. + +@item +@code{must_lt}, @code{must_ne} and @code{must_gt} are irreflexive. + +@item +@code{must_le}, @code{must_eq} and @code{must_ge} are reflexive. +@end itemize + +Also: + +@smallexample +must_lt (@var{a}, @var{b}) == must_gt (@var{b}, @var{a}) +must_le (@var{a}, @var{b}) == must_ge (@var{b}, @var{a}) +must_lt (@var{a}, @var{b}) implies !must_lt (@var{b}, @var{a}) [asymmetry] +must_gt (@var{a}, @var{b}) implies !must_gt (@var{b}, @var{a}) +must_le (@var{a}, @var{b}) && must_le (@var{b}, @var{a}) == must_eq (@var{a}, @var{b}) [== !may_ne (@var{a}, @var{b})] +must_ge (@var{a}, @var{b}) && must_ge (@var{b}, @var{a}) == must_eq (@var{a}, @var{b}) [== !may_ne (@var{a}, @var{b})] +@end smallexample + +@code{must_le} and @code{must_ge} are therefore antisymmetric and are +partial orders. However: + +@smallexample +must_le (@var{a}, @var{b}) does not imply must_lt (@var{a}, @var{b}) || must_eq (@var{a}, @var{b}) +must_ge (@var{a}, @var{b}) does not imply must_gt (@var{a}, @var{b}) || must_eq (@var{a}, @var{b}) +@end smallexample + +For example, @samp{must_le (4, 4 + 4@var{x})} holds because the runtime +indeterminate @var{x} is a nonnegative integer, but neither +@code{must_lt (4, 4 + 4@var{x})} nor @code{must_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 +may_gt (@var{end1}, @var{begin2}) && may_gt (@var{end2}, @var{begin1}) +@end smallexample + +and another is: + +@smallexample +!(must_le (@var{end1}, @var{begin2}) || must_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{must_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{must_le} +partial order. + +@item ordered_min (@var{a}, @var{b}) +Assert that @var{a} and @var{b} are ordered by @code{must_le} and return the +minimum of the two. When using this function, please add a comment explaining +why the values are known to be ordered. + +@item ordered_max (@var{a}, @var{b}) +Assert that @var{a} and @var{b} are ordered by @code{must_le} and return the +maximum of the two. When using this function, please add a comment explaining +why the values are known to be ordered. +@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 must_eq (@var{inner}, @var{outer}) + +@item +otherwise, the subreg is paradoxical if must_le (@var{inner}, @var{outer}) + +@item +otherwise, the subreg is partial if must_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 must_eq (@var{inner}, @var{outer}) + +@item +the subreg is paradoxical if may_lt (@var{inner}, @var{outer}) + +@item +the subreg is partial if may_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{must_eq}. Conversely the best way of checking whether something +is @emph{not} a marker value is @code{may_ne}. + +Thus in the size example just mentioned, @samp{must_eq (size, -1)} would +check for an unknown size and @samp{may_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 length rather than a start +position and an end position; this is because the former is used +much more often than the latter in GCC@. Also, the sizes can be +-1 (or all ones for unsigned sizes) to indicate a range with a known +start position but an unknown size. + +@table @samp +@item ranges_may_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}. + +@item ranges_must_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 @var{value} +is not known to be 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}. +@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. + +@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 +overflow-checking @code{wi} routines: + +@smallexample +wi::neg (@var{p1}, &@var{overflow}) + +wi::add (@var{p1}, @var{p2}, @var{sign}, &@var{overflow}) +wi::sub (@var{p1}, @var{p2}, @var{sign}, &@var{overflow}) +wi::mul (@var{p1}, @var{c2}, @var{sign}, &@var{overflow}) +@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 @var{a} and @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 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 someting 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::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 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}) +Print @var{value} to @var{file} as a decimal value, interpreting +the coefficients according to @var{sign}. 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 salar 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 + Index: gcc/doc/gccint.texi =================================================================== --- gcc/doc/gccint.texi 2017-03-28 16:19:20.000000000 +0100 +++ gcc/doc/gccint.texi 2017-09-06 20:51:42.950082490 +0100 @@ -107,6 +107,7 @@ Additional tutorial information is linke * Testsuites:: GCC testsuites. * Options:: Option specification files. * Passes:: Order of passes, what they do, and what each file is for. +* poly_int:: Representation of runtime sizes and offsets. * GENERIC:: Language-independent representation generated by Front Ends * GIMPLE:: Tuple representation used by Tree SSA optimizers * Tree SSA:: Analysis and optimization of GIMPLE @@ -144,6 +145,7 @@ Additional tutorial information is linke @include sourcebuild.texi @include options.texi @include passes.texi +@include poly-int.texi @include generic.texi @include gimple.texi @include tree-ssa.texi Index: gcc/Makefile.in =================================================================== --- gcc/Makefile.in 2017-08-10 14:36:08.458456783 +0100 +++ gcc/Makefile.in 2017-09-06 20:51:42.949132759 +0100 @@ -3143,7 +3143,7 @@ TEXI_GCCINT_FILES = gccint.texi gcc-comm gnu.texi gpl_v3.texi fdl.texi contrib.texi languages.texi \ sourcebuild.texi gty.texi libgcc.texi cfg.texi tree-ssa.texi \ loop.texi generic.texi gimple.texi plugins.texi optinfo.texi \ - match-and-simplify.texi + match-and-simplify.texi poly-int.texi TEXI_GCCINSTALL_FILES = install.texi install-old.texi fdl.texi \ gcc-common.texi gcc-vers.texi Index: gcc/genmodes.c =================================================================== --- gcc/genmodes.c 2017-08-30 12:20:57.010045759 +0100 +++ gcc/genmodes.c 2017-09-06 20:51:42.952931683 +0100 @@ -781,6 +781,10 @@ create_modes (void) #endif } +#ifndef NUM_POLY_INT_COEFFS +#define NUM_POLY_INT_COEFFS 1 +#endif + /* Processing. */ /* Sort a list of modes into the order needed for the WIDER field: @@ -1246,6 +1250,8 @@ enum machine_mode\n{"); printf ("#define NUM_INT_N_ENTS %d\n", n_int_n_ents); + printf ("#define NUM_POLY_INT_COEFFS %d\n", NUM_POLY_INT_COEFFS); + puts ("\ \n\ #endif /* insn-modes.h */"); Index: gcc/targhooks.h =================================================================== --- gcc/targhooks.h 2017-09-05 20:57:40.746898121 +0100 +++ gcc/targhooks.h 2017-09-06 20:51:42.953881414 +0100 @@ -197,6 +197,7 @@ extern tree default_builtin_tm_load_stor extern int default_memory_move_cost (machine_mode, reg_class_t, bool); extern int default_register_move_cost (machine_mode, reg_class_t, reg_class_t); +extern HOST_WIDE_INT default_estimated_poly_value (poly_int64); extern bool default_use_by_pieces_infrastructure_p (unsigned HOST_WIDE_INT, unsigned int, Index: gcc/targhooks.c =================================================================== --- gcc/targhooks.c 2017-09-05 20:57:40.746898121 +0100 +++ gcc/targhooks.c 2017-09-06 20:51:42.953881414 +0100 @@ -1558,6 +1558,14 @@ default_register_move_cost (machine_mode #endif } +/* The default implementation of TARGET_ESTIMATED_POLY_VALUE. */ + +HOST_WIDE_INT +default_estimated_poly_value (poly_int64 x) +{ + return x.coeffs[0]; +} + /* For hooks which use the MOVE_RATIO macro, this gives the legacy default behavior. SPEED_P is true if we are compiling for speed. */ Index: gcc/target.h =================================================================== --- gcc/target.h 2017-04-18 19:52:34.022581837 +0100 +++ gcc/target.h 2017-09-06 20:51:42.953881414 +0100 @@ -201,6 +201,21 @@ #define HOOKSTRUCT(FRAGMENT) FRAGMENT extern struct gcc_target targetm; +/* Return an estimate of the runtime value of X, for use in things + like cost calculations or profiling frequencies. Note that this + function should never be used in situations where the actual + runtime value is needed for correctness, since the function only + provides a rough guess. */ + +static inline HOST_WIDE_INT +estimated_poly_value (poly_int64 x) +{ + if (NUM_POLY_INT_COEFFS == 1) + return x.coeffs[0]; + else + return targetm.estimated_poly_value (x); +} + #ifdef GCC_TM_H #ifndef CUMULATIVE_ARGS_MAGIC Index: gcc/wide-int.h =================================================================== --- gcc/wide-int.h 2017-08-30 12:10:52.667424437 +0100 +++ gcc/wide-int.h 2017-09-06 20:51:42.953881414 +0100 @@ -275,7 +275,7 @@ #define WI_SIGNED_BINARY_PREDICATE_RESUL /* The type of result produced by a unary operation on type T. */ #define WI_UNARY_RESULT(T) \ - typename wi::unary_traits ::result_type + typename wi::binary_traits ::result_type /* Define a variable RESULT to hold the result of a binary operation on X and Y, which have types T1 and T2 respectively. Define VAL to @@ -369,11 +369,6 @@ #define WIDE_INT_REF_FOR(T) \ enum precision_type P2 = int_traits ::precision_type> struct binary_traits; - /* The result of a unary operation on T is the same as the result of - a binary operation on two values of type T. */ - template - struct unary_traits : public binary_traits {}; - /* Specify the result type for each supported combination of binary inputs. Note that CONST_PRECISION and VAR_PRECISION cannot be mixed, in order to give stronger type checking. When both inputs @@ -3137,6 +3132,20 @@ operator >> (const T1 &x, const T2 &y) return wi::arshift (x, y); } +template +inline WI_SIGNED_SHIFT_RESULT (T1, T2) +operator / (const T1 &x, const T2 &y) +{ + return wi::sdiv_trunc (x, y); +} + +template +inline WI_SIGNED_SHIFT_RESULT (T1, T2) +operator % (const T1 &x, const T2 &y) +{ + return wi::smod_trunc (x, y); +} + template void gt_ggc_mx (generic_wide_int *)