From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20156 invoked by alias); 23 Oct 2017 17:12:41 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 20127 invoked by uid 89); 23 Oct 2017 17:12:41 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-15.0 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KAM_ASCII_DIVIDERS,RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_SPAM,SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-wm0-f47.google.com Received: from mail-wm0-f47.google.com (HELO mail-wm0-f47.google.com) (74.125.82.47) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 23 Oct 2017 17:12:37 +0000 Received: by mail-wm0-f47.google.com with SMTP id u138so11235788wmu.4 for ; Mon, 23 Oct 2017 10:12: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:references:date :in-reply-to:message-id:user-agent:mime-version; bh=Av/k1bCBqpZ9Dv4ViYgK5qFGBhp4Tx/QwYsGWEc7Ng0=; b=L26ONJuhX9kp37FNmZLAAEnBC4AC3MRiQ7WRMGcrW/SW0GNPglk4KVEizkpeDOKuN+ 3jWgxVqo+XNbEHoDNBXuclTZAhPil7pYcpaGeAEux/nlKSUXMeZqUPZlHWcV1SWxuKlf v8YE77gIVrnMWnm9Tgtvdsz/kZTEAQ4NreXPkVsA9a1Xz6KFPKvwGGNPGyBq7csDOGa9 1zk4aJgcBCJdBVFAXyCKE2BWo3KqO00QFaXkZRSofZUoASJ1E7LEUQZP7/jwMgM4lvK3 s6mt5htGx2Dg3YjClzvz9U4uVpTeP1MSee9SBsTuD666hkMkQuPRWkxrnY64ft2z2wcZ hN7g== X-Gm-Message-State: AMCzsaVER04lhj+oDPih9l8I1DwAXH7HP8D+dL6aNjJ4V3Obbz09sLbF T/4A+Ra+Mbsnw354WEe0PIP2Dho0umk= X-Google-Smtp-Source: ABhQp+SCR1VthGH+4kViAekPMzV0PtQnETNM339WA2BW053mIam3D+yReEECwWJRgki7DXM1KdD+sA== X-Received: by 10.28.71.90 with SMTP id u87mr3779736wma.91.1508778755070; Mon, 23 Oct 2017 10:12:35 -0700 (PDT) Received: from localhost ([2.26.27.199]) by smtp.gmail.com with ESMTPSA id c142sm6519641wmh.39.2017.10.23.10.12.33 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 23 Oct 2017 10:12:34 -0700 (PDT) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@linaro.org Subject: [031/nnn] poly_int: aff_tree References: <871sltvm7r.fsf@linaro.org> Date: Mon, 23 Oct 2017 17:13:00 -0000 In-Reply-To: <871sltvm7r.fsf@linaro.org> (Richard Sandiford's message of "Mon, 23 Oct 2017 17:54:32 +0100") Message-ID: <8760b5pz3y.fsf@linaro.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-SW-Source: 2017-10/txt/msg01532.txt.bz2 This patch changes the type of aff_tree::offset from widest_int to poly_widest_int and adjusts the function interfaces in the same way. 2017-10-23 Richard Sandiford Alan Hayward David Sherwood gcc/ * tree-affine.h (aff_tree::offset): Change from widest_int to poly_widest_int. (wide_int_ext_for_comb): Delete. (aff_combination_const, aff_comb_cannot_overlap_p): Take the constants as poly_widest_int rather than widest_int. (aff_combination_constant_multiple_p): Return the multiplier as a poly_widest_int. (aff_combination_zero_p, aff_combination_singleton_var_p): Handle polynomial offsets. * tree-affine.c (wide_int_ext_for_comb): Make original widest_int version static and add an overload for poly_widest_int. (aff_combination_const, aff_combination_add_cst) (wide_int_constant_multiple_p, aff_comb_cannot_overlap_p): Take the constants as poly_widest_int rather than widest_int. (tree_to_aff_combination): Generalize INTEGER_CST case to poly_int_tree_p. (aff_combination_to_tree): Track offsets as poly_widest_ints. (aff_combination_add_product, aff_combination_mult): Handle polynomial offsets. (aff_combination_constant_multiple_p): Return the multiplier as a poly_widest_int. * tree-predcom.c (determine_offset): Return the offset as a poly_widest_int. (split_data_refs_to_components, suitable_component_p): Update accordingly. (valid_initializer_p): Update call to aff_combination_constant_multiple_p. * tree-ssa-address.c (addr_to_parts): Handle polynomial offsets. * tree-ssa-loop-ivopts.c (get_address_cost_ainc): Take the step as a poly_int64 rather than a HOST_WIDE_INT. (get_address_cost): Handle polynomial offsets. (iv_elimination_compare_lt): Likewise. (rewrite_use_nonlinear_expr): Likewise. Index: gcc/tree-affine.h =================================================================== --- gcc/tree-affine.h 2017-10-23 17:07:40.771877812 +0100 +++ gcc/tree-affine.h 2017-10-23 17:17:03.206794823 +0100 @@ -43,7 +43,7 @@ struct aff_tree tree type; /* Constant offset. */ - widest_int offset; + poly_widest_int offset; /* Number of elements of the combination. */ unsigned n; @@ -64,8 +64,7 @@ struct aff_tree struct name_expansion; -widest_int wide_int_ext_for_comb (const widest_int &, aff_tree *); -void aff_combination_const (aff_tree *, tree, const widest_int &); +void aff_combination_const (aff_tree *, tree, const poly_widest_int &); void aff_combination_elt (aff_tree *, tree, tree); void aff_combination_scale (aff_tree *, const widest_int &); void aff_combination_mult (aff_tree *, aff_tree *, aff_tree *); @@ -76,14 +75,15 @@ void aff_combination_convert (aff_tree * void tree_to_aff_combination (tree, tree, aff_tree *); tree aff_combination_to_tree (aff_tree *); void unshare_aff_combination (aff_tree *); -bool aff_combination_constant_multiple_p (aff_tree *, aff_tree *, widest_int *); +bool aff_combination_constant_multiple_p (aff_tree *, aff_tree *, + poly_widest_int *); void aff_combination_expand (aff_tree *, hash_map **); void tree_to_aff_combination_expand (tree, tree, aff_tree *, hash_map **); tree get_inner_reference_aff (tree, aff_tree *, widest_int *); void free_affine_expand_cache (hash_map **); -bool aff_comb_cannot_overlap_p (aff_tree *, const widest_int &, - const widest_int &); +bool aff_comb_cannot_overlap_p (aff_tree *, const poly_widest_int &, + const poly_widest_int &); /* Debugging functions. */ void debug_aff (aff_tree *); @@ -102,7 +102,7 @@ aff_combination_zero_p (aff_tree *aff) if (!aff) return true; - if (aff->n == 0 && aff->offset == 0) + if (aff->n == 0 && known_zero (aff->offset)) return true; return false; @@ -121,7 +121,7 @@ aff_combination_const_p (aff_tree *aff) aff_combination_singleton_var_p (aff_tree *aff) { return (aff->n == 1 - && aff->offset == 0 + && known_zero (aff->offset) && (aff->elts[0].coef == 1 || aff->elts[0].coef == -1)); } #endif /* GCC_TREE_AFFINE_H */ Index: gcc/tree-affine.c =================================================================== --- gcc/tree-affine.c 2017-10-23 17:07:40.771877812 +0100 +++ gcc/tree-affine.c 2017-10-23 17:17:03.206794823 +0100 @@ -34,12 +34,20 @@ Free Software Foundation; either version /* Extends CST as appropriate for the affine combinations COMB. */ -widest_int +static widest_int wide_int_ext_for_comb (const widest_int &cst, tree type) { return wi::sext (cst, TYPE_PRECISION (type)); } +/* Likewise for polynomial offsets. */ + +static poly_widest_int +wide_int_ext_for_comb (const poly_widest_int &cst, tree type) +{ + return wi::sext (cst, TYPE_PRECISION (type)); +} + /* Initializes affine combination COMB so that its value is zero in TYPE. */ static void @@ -57,7 +65,7 @@ aff_combination_zero (aff_tree *comb, tr /* Sets COMB to CST. */ void -aff_combination_const (aff_tree *comb, tree type, const widest_int &cst) +aff_combination_const (aff_tree *comb, tree type, const poly_widest_int &cst) { aff_combination_zero (comb, type); comb->offset = wide_int_ext_for_comb (cst, comb->type);; @@ -190,7 +198,7 @@ aff_combination_add_elt (aff_tree *comb, /* Adds CST to C. */ static void -aff_combination_add_cst (aff_tree *c, const widest_int &cst) +aff_combination_add_cst (aff_tree *c, const poly_widest_int &cst) { c->offset = wide_int_ext_for_comb (c->offset + cst, c->type); } @@ -268,10 +276,6 @@ tree_to_aff_combination (tree expr, tree code = TREE_CODE (expr); switch (code) { - case INTEGER_CST: - aff_combination_const (comb, type, wi::to_widest (expr)); - return; - case POINTER_PLUS_EXPR: tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp); @@ -423,7 +427,14 @@ tree_to_aff_combination (tree expr, tree break; default: - break; + { + if (poly_int_tree_p (expr)) + { + aff_combination_const (comb, type, wi::to_poly_widest (expr)); + return; + } + break; + } } aff_combination_elt (comb, type, expr); @@ -478,7 +489,8 @@ aff_combination_to_tree (aff_tree *comb) { tree type = comb->type, base = NULL_TREE, expr = NULL_TREE; unsigned i; - widest_int off, sgn; + poly_widest_int off; + int sgn; gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE); @@ -502,7 +514,7 @@ aff_combination_to_tree (aff_tree *comb) /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is unsigned. */ - if (wi::neg_p (comb->offset)) + if (must_lt (comb->offset, 0)) { off = -comb->offset; sgn = -1; @@ -588,7 +600,19 @@ aff_combination_add_product (aff_tree *c } if (val) - aff_combination_add_elt (r, val, coef * c->offset); + { + if (c->offset.is_constant ()) + /* Access coeffs[0] directly, for efficiency. */ + aff_combination_add_elt (r, val, coef * c->offset.coeffs[0]); + else + { + /* c->offset is polynomial, so multiply VAL rather than COEF + by it. */ + tree offset = wide_int_to_tree (TREE_TYPE (val), c->offset); + val = fold_build2 (MULT_EXPR, TREE_TYPE (val), val, offset); + aff_combination_add_elt (r, val, coef); + } + } else aff_combination_add_cst (r, coef * c->offset); } @@ -607,7 +631,15 @@ aff_combination_mult (aff_tree *c1, aff_ aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r); if (c2->rest) aff_combination_add_product (c1, 1, c2->rest, r); - aff_combination_add_product (c1, c2->offset, NULL, r); + if (c2->offset.is_constant ()) + /* Access coeffs[0] directly, for efficiency. */ + aff_combination_add_product (c1, c2->offset.coeffs[0], NULL, r); + else + { + /* c2->offset is polynomial, so do the multiplication in tree form. */ + tree offset = wide_int_to_tree (c2->type, c2->offset); + aff_combination_add_product (c1, 1, offset, r); + } } /* Returns the element of COMB whose value is VAL, or NULL if no such @@ -776,27 +808,28 @@ free_affine_expand_cache (hash_mapn == 0 && val->offset == 0) + if (val->n == 0 && known_zero (val->offset)) { *mult = 0; return true; @@ -927,23 +960,26 @@ get_inner_reference_aff (tree ref, aff_t size SIZE2 at position DIFF cannot overlap. */ bool -aff_comb_cannot_overlap_p (aff_tree *diff, const widest_int &size1, - const widest_int &size2) +aff_comb_cannot_overlap_p (aff_tree *diff, const poly_widest_int &size1, + const poly_widest_int &size2) { /* Unless the difference is a constant, we fail. */ if (diff->n != 0) return false; - if (wi::neg_p (diff->offset)) + if (!ordered_p (diff->offset, 0)) + return false; + + if (may_lt (diff->offset, 0)) { /* The second object is before the first one, we succeed if the last element of the second object is before the start of the first one. */ - return wi::neg_p (diff->offset + size2 - 1); + return must_le (diff->offset + size2, 0); } else { /* We succeed if the second object starts after the first one ends. */ - return size1 <= diff->offset; + return must_le (size1, diff->offset); } } Index: gcc/tree-predcom.c =================================================================== --- gcc/tree-predcom.c 2017-10-23 17:07:40.771877812 +0100 +++ gcc/tree-predcom.c 2017-10-23 17:17:03.207794688 +0100 @@ -688,7 +688,7 @@ aff_combination_dr_offset (struct data_r static bool determine_offset (struct data_reference *a, struct data_reference *b, - widest_int *off) + poly_widest_int *off) { aff_tree diff, baseb, step; tree typea, typeb; @@ -797,7 +797,7 @@ split_data_refs_to_components (struct lo FOR_EACH_VEC_ELT (depends, i, ddr) { - widest_int dummy_off; + poly_widest_int dummy_off; if (DDR_ARE_DEPENDENT (ddr) == chrec_known) continue; @@ -956,7 +956,11 @@ suitable_component_p (struct loop *loop, for (i = 1; comp->refs.iterate (i, &a); i++) { - if (!determine_offset (first->ref, a->ref, &a->offset)) + /* Polynomial offsets are no use, since we need to know the + gap between iteration numbers at compile time. */ + poly_widest_int offset; + if (!determine_offset (first->ref, a->ref, &offset) + || !offset.is_constant (&a->offset)) return false; enum ref_step_type a_step; @@ -1158,7 +1162,7 @@ valid_initializer_p (struct data_referen unsigned distance, struct data_reference *root) { aff_tree diff, base, step; - widest_int off; + poly_widest_int off; /* Both REF and ROOT must be accessing the same object. */ if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0)) @@ -1186,7 +1190,7 @@ valid_initializer_p (struct data_referen if (!aff_combination_constant_multiple_p (&diff, &step, &off)) return false; - if (off != distance) + if (may_ne (off, distance)) return false; return true; Index: gcc/tree-ssa-address.c =================================================================== --- gcc/tree-ssa-address.c 2017-10-23 17:17:01.433034358 +0100 +++ gcc/tree-ssa-address.c 2017-10-23 17:17:03.207794688 +0100 @@ -693,7 +693,7 @@ addr_to_parts (tree type, aff_tree *addr parts->index = NULL_TREE; parts->step = NULL_TREE; - if (addr->offset != 0) + if (maybe_nonzero (addr->offset)) parts->offset = wide_int_to_tree (sizetype, addr->offset); else parts->offset = NULL_TREE; Index: gcc/tree-ssa-loop-ivopts.c =================================================================== --- gcc/tree-ssa-loop-ivopts.c 2017-10-23 17:11:40.249954781 +0100 +++ gcc/tree-ssa-loop-ivopts.c 2017-10-23 17:17:03.208794553 +0100 @@ -4232,7 +4232,7 @@ struct ainc_cost_data }; static comp_cost -get_address_cost_ainc (HOST_WIDE_INT ainc_step, HOST_WIDE_INT ainc_offset, +get_address_cost_ainc (poly_int64 ainc_step, poly_int64 ainc_offset, machine_mode addr_mode, machine_mode mem_mode, addr_space_t as, bool speed) { @@ -4306,13 +4306,13 @@ get_address_cost_ainc (HOST_WIDE_INT ain } HOST_WIDE_INT msize = GET_MODE_SIZE (mem_mode); - if (ainc_offset == 0 && msize == ainc_step) + if (known_zero (ainc_offset) && must_eq (msize, ainc_step)) return comp_cost (data->costs[AINC_POST_INC], 0); - if (ainc_offset == 0 && msize == -ainc_step) + if (known_zero (ainc_offset) && must_eq (msize, -ainc_step)) return comp_cost (data->costs[AINC_POST_DEC], 0); - if (ainc_offset == msize && msize == ainc_step) + if (must_eq (ainc_offset, msize) && must_eq (msize, ainc_step)) return comp_cost (data->costs[AINC_PRE_INC], 0); - if (ainc_offset == -msize && msize == -ainc_step) + if (must_eq (ainc_offset, -msize) && must_eq (msize, -ainc_step)) return comp_cost (data->costs[AINC_PRE_DEC], 0); return infinite_cost; @@ -4355,7 +4355,7 @@ get_address_cost (struct ivopts_data *da if (ratio != 1 && !valid_mem_ref_p (mem_mode, as, &parts)) parts.step = NULL_TREE; - if (aff_inv->offset != 0) + if (maybe_nonzero (aff_inv->offset)) { parts.offset = wide_int_to_tree (sizetype, aff_inv->offset); /* Addressing mode "base + index [<< scale] + offset". */ @@ -4388,10 +4388,12 @@ get_address_cost (struct ivopts_data *da } else { - if (can_autoinc && ratio == 1 && cst_and_fits_in_hwi (cand->iv->step)) + poly_int64 ainc_step; + if (can_autoinc + && ratio == 1 + && ptrdiff_tree_p (cand->iv->step, &ainc_step)) { - HOST_WIDE_INT ainc_step = int_cst_value (cand->iv->step); - HOST_WIDE_INT ainc_offset = (aff_inv->offset).to_shwi (); + poly_int64 ainc_offset = (aff_inv->offset).force_shwi (); if (stmt_after_increment (data->current_loop, cand, use->stmt)) ainc_offset += ainc_step; @@ -4949,7 +4951,7 @@ iv_elimination_compare_lt (struct ivopts aff_combination_scale (&tmpa, -1); aff_combination_add (&tmpb, &tmpa); aff_combination_add (&tmpb, &nit); - if (tmpb.n != 0 || tmpb.offset != 1) + if (tmpb.n != 0 || may_ne (tmpb.offset, 1)) return false; /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not @@ -6846,7 +6848,7 @@ rewrite_use_nonlinear_expr (struct ivopt unshare_aff_combination (&aff_var); /* Prefer CSE opportunity than loop invariant by adding offset at last so that iv_uses have different offsets can be CSEed. */ - widest_int offset = aff_inv.offset; + poly_widest_int offset = aff_inv.offset; aff_inv.offset = 0; gimple_seq stmt_list = NULL, seq = NULL;