From patchwork Mon Nov 25 12:24:06 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 293904 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 2A9612C00CC for ; Mon, 25 Nov 2013 23:24:27 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; q=dns; s=default; b=e/8HxZP/t5mhqY8Uly AUMsl+DM16e/AWSWrfoJ7bwaG3C3rIL9mzmq/nPGOiFgfIwLlbZC3QtnwhPsyWpL 5LAi7XIJgRhhGwDg7+cJFBNItAmT7UsschBZa0eIct75swpyIH8k5BRPWexycGpt GENbJtwOSPVDR0SvS9ZkvWBcQ= 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 :mime-version:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; s=default; bh=63QZlMISSw3BWen0nslk9VtM WPw=; b=ZIq5FWIdri7QHwyYwoGIq1f6RxQEk4kpS2DsR36hL0yxco7WzPFRPQ3a ojhZ0YTS6YUIxd2YmPxpVpX021pU29oHnXr63DLx3lIZ/YoBV8gsXB970jwX8AL4 hDq7xZSH6tmkCbT/r8B4MuUez0Rd5mEhjPmjkpIPoxd7GR17Sgg= Received: (qmail 28845 invoked by alias); 25 Nov 2013 12:24:17 -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 28825 invoked by uid 89); 25 Nov 2013 12:24:17 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=2.9 required=5.0 tests=AWL, BAYES_95, FREEMAIL_FROM, RDNS_NONE, SPF_PASS autolearn=no version=3.3.2 X-HELO: mail-wg0-f49.google.com Received: from Unknown (HELO mail-wg0-f49.google.com) (74.125.82.49) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Mon, 25 Nov 2013 12:24:15 +0000 Received: by mail-wg0-f49.google.com with SMTP id x12so3812755wgg.16 for ; Mon, 25 Nov 2013 04:24:06 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.180.210.134 with SMTP id mu6mr13391802wic.37.1385382246322; Mon, 25 Nov 2013 04:24:06 -0800 (PST) Received: by 10.195.12.114 with HTTP; Mon, 25 Nov 2013 04:24:06 -0800 (PST) In-Reply-To: <9B8BAA2C-F386-424D-9D9D-CE711FFD8D10@comcast.net> References: <9B8BAA2C-F386-424D-9D9D-CE711FFD8D10@comcast.net> Date: Mon, 25 Nov 2013 13:24:06 +0100 Message-ID: Subject: Re: wide-int, tree From: Richard Biener To: Mike Stump Cc: "gcc-patches@gcc.gnu.org Patches" , Kenneth Zadeck X-IsSubscribed: yes On Sat, Nov 23, 2013 at 8:22 PM, Mike Stump wrote: > Richi has asked the we break the wide-int patch so that the individual port and front end maintainers can review their parts without have to go through the entire patch. This patch covers the tree code. > > Ok? Note that INT_CST_LT and INT_CST_LT_UNSIGNED were supposed to be very fast. Now you made them #define INT_CST_LT(A, B) (wi::lts_p (wi::to_widest (A), wi::to_widest (B))) which a) doesn't look the same to me and b) hides complexity. So why not write if (TREE_CODE (val) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST) if (TYPE_UNSIGNED (...) return wi::ltu_p (val, va2); else return wi::lts_p (val, val2); ? @@ -6966,12 +6975,7 @@ tree_int_cst_lt (const_tree t1, const_tree t2) int tree_int_cst_compare (const_tree t1, const_tree t2) { - if (tree_int_cst_lt (t1, t2)) - return -1; - else if (tree_int_cst_lt (t2, t1)) - return 1; - else - return 0; + return wi::cmps (wi::to_widest (t1), wi::to_widest (t2)); } /* Return true if T is an INTEGER_CST whose numerical value (extended How does this work for comparing UHWI_MAX to 0 for example? Looking at template inline int wi::cmps (const T1 &x, const T2 &y) { unsigned int precision = get_binary_precision (x, y); WIDE_INT_REF_FOR (T1) xi (x, precision); WIDE_INT_REF_FOR (T2) yi (y, precision); if (precision <= HOST_BITS_PER_WIDE_INT) { HOST_WIDE_INT xl = xi.to_shwi (); HOST_WIDE_INT yl = yi.to_shwi (); if (xl < yl) return -1; this seems to happily return -1 instead of 1? Similar issues elsewhere where you change compares to unconditonally perform signed compares. (it's at least non-obvious to me). Ah, the to_widest () will make it XImode * 4 extended and thus get_precision returns 2048 (or so) so we don't take the shortcut (which means it's slow). Shouldn't the shortcuts be taken on 'len' == 1 rather than precision <= HWI? Side-note: we have too many ways to compare trees / integers @@ -8600,18 +8577,7 @@ retry: /* Check if c <= type_high_bound. */ if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST) { - dd = tree_to_double_int (type_high_bound); - if (unsc != TYPE_UNSIGNED (TREE_TYPE (type_high_bound))) - { - int c_neg = (!unsc && dc.is_negative ()); - int t_neg = (unsc && dd.is_negative ()); - - if (t_neg && !c_neg) - return false; - if ((t_neg || !c_neg) && dc.ugt (dd)) - return false; - } - else if (dc.cmp (dd, unsc) > 0) + if (INT_CST_LT (type_high_bound, c)) return false; please eliminate INT_CST_LT in favor of tree_int_cst_lt (which just calls INT_CST_LT). And INT_CST_LE as well. The rest of the patch looks ok to me. I suggest to produce patches for the wide-int branch addressing review comments. Thanks, Richard. diff --git a/gcc/tree-affine.h b/gcc/tree-affine.h index 86f90d8..961b9a6 100644 --- a/gcc/tree-affine.h +++ b/gcc/tree-affine.h @@ -30,7 +32,7 @@ struct aff_comb_elt tree val; /* Its coefficient in the combination. */ - double_int coef; + widest_int coef; }; typedef struct affine_tree_combination @@ -39,7 +41,7 @@ typedef struct affine_tree_combination tree type; /* Constant offset. */ - double_int offset; + widest_int offset; /* Number of elements of the combination. */ unsigned n; increases size of *aff_tree from 232 to 808 bytes. Most of this is waste, killing cache locality. Now you are lucky, aff_tree mostly lives on the stack (though I had patches to make LIM cache them as creating them is expensive...). Not objecting to the change at this very moment, but we desparately need some external storage solution for these kind of uses. Oh, and shrink that widest_int ... (x86_64 and XImode ...) diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c index afc1a6a..91a14e4 100644 --- a/gcc/tree-chrec.c +++ b/gcc/tree-chrec.c @@ -479,7 +479,6 @@ chrec_fold_multiply (tree type, static tree tree_fold_binomial (tree type, tree n, unsigned int k) { - double_int num, denom, idx, di_res; bool overflow; unsigned int i; tree res; @@ -491,20 +490,20 @@ tree_fold_binomial (tree type, tree n, unsigned int k) return fold_convert (type, n); /* Numerator = n. */ - num = TREE_INT_CST (n); + wide_int num = n; /* Check that k <= n. */ - if (num.ult (double_int::from_uhwi (k))) + if (wi::ltu_p (num, k)) return NULL_TREE; compare_tree_int (n, k) < 0 may be cheaper here diff --git a/gcc/tree-predcom.c b/gcc/tree-predcom.c index 0d3c66c..f257d52 100644 --- a/gcc/tree-predcom.c +++ b/gcc/tree-predcom.c @@ -217,6 +217,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-pass.h" #include "tree-affine.h" #include "tree-inline.h" +#include "wide-int-print.h" /* The maximum number of iterations between the considered memory references. */ @@ -244,7 +245,7 @@ typedef struct dref_d unsigned distance; /* Number of iterations offset from the first reference in the component. */ - double_int offset; + widest_int offset; another one. diff --git a/gcc/tree-streamer-in.c b/gcc/tree-streamer-in.c index 560d4f8..a70c767 100644 --- a/gcc/tree-streamer-in.c +++ b/gcc/tree-streamer-in.c @@ -147,8 +147,9 @@ unpack_ts_base_value_fields (struct bitpack_d *bp, tree expr) static void unpack_ts_int_cst_value_fields (struct bitpack_d *bp, tree expr) { - TREE_INT_CST_LOW (expr) = bp_unpack_var_len_unsigned (bp); - TREE_INT_CST_HIGH (expr) = bp_unpack_var_len_int (bp); + int i; + for (i = 0; i < TREE_INT_CST_EXT_NUNITS (expr); i++) + TREE_INT_CST_ELT (expr, i) = bp_unpack_var_len_int (bp); } that's less than optimal - only the very last used word should use var_len_int, the others should use unsigned. @@ -958,6 +961,12 @@ streamer_write_tree_header (struct output_block *ob, tree expr) streamer_write_uhwi (ob, BINFO_N_BASE_BINFOS (expr)); else if (TREE_CODE (expr) == CALL_EXPR) streamer_write_uhwi (ob, call_expr_nargs (expr)); + else if (CODE_CONTAINS_STRUCT (code, TS_INT_CST)) + { + gcc_checking_assert (TREE_INT_CST_NUNITS (expr)); + streamer_write_uhwi (ob, TREE_INT_CST_NUNITS (expr)); + streamer_write_uhwi (ob, TREE_INT_CST_EXT_NUNITS (expr)); + } isn't ext_nunits always either nunits or nunits + 1? So it should be sufficient to write a single bit in the tree_base bitpack and only write the nunits that are required for the actual allocation in write_tree_header, not both. @@ -967,9 +976,16 @@ streamer_write_tree_header (struct output_block *ob, tree expr) void streamer_write_integer_cst (struct output_block *ob, tree cst, bool ref_p) { + int i; + int len = TREE_INT_CST_NUNITS (cst); gcc_assert (!TREE_OVERFLOW (cst)); streamer_write_record_start (ob, LTO_integer_cst); stream_write_tree (ob, TREE_TYPE (cst), ref_p); - streamer_write_uhwi (ob, TREE_INT_CST_LOW (cst)); - streamer_write_hwi (ob, TREE_INT_CST_HIGH (cst)); + /* We're effectively streaming a non-sign-extended wide_int here, + so there's no need to stream TREE_INT_CST_EXT_NUNITS or any + array members beyond LEN. We'll recreate the tree from the + wide_int and the type. */ + streamer_write_uhwi (ob, len); + for (i = 0; i < len; i++) + streamer_write_hwi (ob, TREE_INT_CST_ELT (cst, i)); } and that's duplicate writing of TREE_INT_CST_NUNITS ('len'). diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index 494d48e..fc0b574 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -445,7 +445,13 @@ emit_case_bit_tests (gimple swtch, tree index_expr, if (const & csui) goto target */ for (k = 0; k < count; k++) { - tmp = build_int_cst_wide (word_type_node, test[k].lo, test[k].hi); + HOST_WIDE_INT a[2]; + + a[0] = test[k].lo; + a[1] = test[k].hi; + tmp = wide_int_to_tree (word_type_node, + wide_int::from_array (a, 2, + TYPE_PRECISION (word_type_node))); tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp); tmp = force_gimple_operand_gsi (&gsi, tmp, /*simple=*/true, NULL_TREE, and that's truly odd code - it seems to expect that two HWIs fit word_type_node. Completely wrong on i?86 for example. Please add a /* ??? */ comment here at least. @@ -885,7 +891,7 @@ build_constructors (gimple swtch, struct switch_conv_info *info) info->constructors[k]->quick_push (elt); } - pos = int_const_binop (PLUS_EXPR, pos, integer_one_node); + pos = int_const_binop (PLUS_EXPR, pos, build_int_cst (TREE_TYPE (pos), 1)); } gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs))); reminds me that we want a HWI overload for int_const_binop ;) Not sure if wide_int_to_tree (TREE_TYPE (pos), wi::add (pos, 1)) is better than that though. diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 4a24c66..f3e0ffe 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -1141,15 +1142,7 @@ operand_less_p (tree val, tree val2) { /* LT is folded faster than GE and others. Inline the common case. */ if (TREE_CODE (val) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST) - { - if (TYPE_UNSIGNED (TREE_TYPE (val))) - return INT_CST_LT_UNSIGNED (val, val2); - else - { - if (INT_CST_LT (val, val2)) - return 1; - } - } + return INT_CST_LT (val, val2); else { tree tcmp;