From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 89006 invoked by alias); 23 Oct 2017 17:25:52 -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 88493 invoked by uid 89); 23 Oct 2017 17:25:52 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.0 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_2,GIT_PATCH_3,KAM_ASCII_DIVIDERS,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.2 spammy=a2, A2, A1, a1 X-HELO: mail-wm0-f44.google.com Received: from mail-wm0-f44.google.com (HELO mail-wm0-f44.google.com) (74.125.82.44) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 23 Oct 2017 17:25:49 +0000 Received: by mail-wm0-f44.google.com with SMTP id p75so10964356wmg.3 for ; Mon, 23 Oct 2017 10:25:49 -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=Cvp2KEVyb3jPdrC9TZI99NwZwEm0hBwuMO8lIdAsEnY=; b=PeSviUziX44/i0iZISDNg4IvhBKJLeSQmJ97k09Pzqbej4+oh0YQY9Iiaq7LBrIdG5 4tv3J+RcDz/vzElOWiGFQuUt+JVTCSPvWP1FOPRhPebi0oE1j1stCdOxglgF4pmsAxSu KrhzSwuFTZWRFC0FJ6EI+0t96q8sk51i0DysOogWYAwIpUwtGjid5PAGXSUbNauE8ZJe BeZzi0gLzArYF1hDrWKw0pr9NYvj/k08VURh6p3VqSqEg9F0qh6TOafEU9SobZDNCcbr quYmxTEZ7fmxF955mchTLjHf8sXgg0rzTCzcsVIOgtgBgG+27lbUB+FYGwdMG5iZUr/z bu4Q== X-Gm-Message-State: AMCzsaXWhsEohqKYDK0SMLG21oUYDCvC5+XCVG5uPjeFP7Zt9S4jZY0T bzLRzO4YIciyGoPgAcALWeAKtLj1Qw0= X-Google-Smtp-Source: ABhQp+R040kB5NiDJ82feIKQ7uabf7evpvKXUYLAMtkYOtfAfcqCnpa1NTaeyZsli19vxDJsvK1KaQ== X-Received: by 10.28.32.136 with SMTP id g130mr6395364wmg.102.1508779547438; Mon, 23 Oct 2017 10:25:47 -0700 (PDT) Received: from localhost ([2.26.27.199]) by smtp.gmail.com with ESMTPSA id 68sm4342887wmh.2.2017.10.23.10.25.46 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 23 Oct 2017 10:25:46 -0700 (PDT) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@linaro.org Subject: [062/nnn] poly_int: prune_runtime_alias_test_list References: <871sltvm7r.fsf@linaro.org> Date: Mon, 23 Oct 2017 17:26:00 -0000 In-Reply-To: <871sltvm7r.fsf@linaro.org> (Richard Sandiford's message of "Mon, 23 Oct 2017 17:54:32 +0100") Message-ID: <87fua9kc86.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/msg01563.txt.bz2 This patch makes prune_runtime_alias_test_list take the iteration factor as a poly_int and tracks polynomial offsets internally as well. 2017-10-23 Richard Sandiford Alan Hayward David Sherwood gcc/ * tree-data-ref.h (prune_runtime_alias_test_list): Take the factor as a poly_uint64 rather than an unsigned HOST_WIDE_INT. * tree-data-ref.c (prune_runtime_alias_test_list): Likewise. Track polynomial offsets. Index: gcc/tree-data-ref.h =================================================================== --- gcc/tree-data-ref.h 2017-10-13 10:23:39.775145588 +0100 +++ gcc/tree-data-ref.h 2017-10-23 17:22:25.492282436 +0100 @@ -472,7 +472,7 @@ extern bool dr_equal_offsets_p (struct d extern bool runtime_alias_check_p (ddr_p, struct loop *, bool); extern int data_ref_compare_tree (tree, tree); extern void prune_runtime_alias_test_list (vec *, - unsigned HOST_WIDE_INT); + poly_uint64); extern void create_runtime_alias_checks (struct loop *, vec *, tree*); /* Return true when the base objects of data references A and B are Index: gcc/tree-data-ref.c =================================================================== --- gcc/tree-data-ref.c 2017-10-23 17:22:18.231825655 +0100 +++ gcc/tree-data-ref.c 2017-10-23 17:22:25.492282436 +0100 @@ -1417,7 +1417,7 @@ comp_dr_with_seg_len_pair (const void *p void prune_runtime_alias_test_list (vec *alias_pairs, - unsigned HOST_WIDE_INT factor) + poly_uint64 factor) { /* Sort the collected data ref pairs so that we can scan them once to combine all possible aliasing checks. */ @@ -1462,51 +1462,63 @@ prune_runtime_alias_test_list (vecdr), DR_BASE_ADDRESS (dr_a2->dr), 0) || !operand_equal_p (DR_OFFSET (dr_a1->dr), DR_OFFSET (dr_a2->dr), 0) - || !tree_fits_shwi_p (DR_INIT (dr_a1->dr)) - || !tree_fits_shwi_p (DR_INIT (dr_a2->dr))) + || !poly_int_tree_p (DR_INIT (dr_a1->dr), &init_a1) + || !poly_int_tree_p (DR_INIT (dr_a2->dr), &init_a2)) continue; + /* Don't combine if we can't tell which one comes first. */ + if (!ordered_p (init_a1, init_a2)) + continue; + + /* Make sure dr_a1 starts left of dr_a2. */ + if (may_gt (init_a1, init_a2)) + { + std::swap (*dr_a1, *dr_a2); + std::swap (init_a1, init_a2); + } + /* Only merge const step data references. */ - if (TREE_CODE (DR_STEP (dr_a1->dr)) != INTEGER_CST - || TREE_CODE (DR_STEP (dr_a2->dr)) != INTEGER_CST) + poly_int64 step_a1, step_a2; + if (!poly_int_tree_p (DR_STEP (dr_a1->dr), &step_a1) + || !poly_int_tree_p (DR_STEP (dr_a2->dr), &step_a2)) continue; - /* DR_A1 and DR_A2 must goes in the same direction. */ - if (tree_int_cst_compare (DR_STEP (dr_a1->dr), size_zero_node) - != tree_int_cst_compare (DR_STEP (dr_a2->dr), size_zero_node)) + bool neg_step = may_lt (step_a1, 0) || may_lt (step_a2, 0); + + /* DR_A1 and DR_A2 must go in the same direction. */ + if (neg_step && (may_gt (step_a1, 0) || may_gt (step_a2, 0))) continue; - bool neg_step - = (tree_int_cst_compare (DR_STEP (dr_a1->dr), size_zero_node) < 0); + poly_uint64 seg_len_a1 = 0, seg_len_a2 = 0; + bool const_seg_len_a1 = poly_int_tree_p (dr_a1->seg_len, + &seg_len_a1); + bool const_seg_len_a2 = poly_int_tree_p (dr_a2->seg_len, + &seg_len_a2); /* We need to compute merged segment length at compilation time for dr_a1 and dr_a2, which is impossible if either one has non-const segment length. */ - if ((!tree_fits_uhwi_p (dr_a1->seg_len) - || !tree_fits_uhwi_p (dr_a2->seg_len)) - && tree_int_cst_compare (DR_STEP (dr_a1->dr), - DR_STEP (dr_a2->dr)) != 0) + if ((!const_seg_len_a1 || !const_seg_len_a2) + && may_ne (step_a1, step_a2)) continue; - /* Make sure dr_a1 starts left of dr_a2. */ - if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr))) - std::swap (*dr_a1, *dr_a2); - bool do_remove = false; - wide_int diff = (wi::to_wide (DR_INIT (dr_a2->dr)) - - wi::to_wide (DR_INIT (dr_a1->dr))); - wide_int min_seg_len_b; + poly_uint64 diff = init_a2 - init_a1; + poly_uint64 min_seg_len_b; tree new_seg_len; - if (TREE_CODE (dr_b1->seg_len) == INTEGER_CST) - min_seg_len_b = wi::abs (wi::to_wide (dr_b1->seg_len)); - else - min_seg_len_b - = factor * wi::abs (wi::to_wide (DR_STEP (dr_b1->dr))); + if (!poly_int_tree_p (dr_b1->seg_len, &min_seg_len_b)) + { + tree step_b = DR_STEP (dr_b1->dr); + if (!tree_fits_shwi_p (step_b)) + continue; + min_seg_len_b = factor * abs_hwi (tree_to_shwi (step_b)); + } /* Now we try to merge alias check dr_a1 & dr_b and dr_a2 & dr_b. @@ -1543,26 +1555,24 @@ prune_runtime_alias_test_list (vecdr))); - tree size_a2 = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a2->dr))); - diff += wi::to_wide (size_a2) - wi::to_wide (size_a1); + diff += tree_to_poly_uint64 + (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a2->dr)))); + diff -= tree_to_poly_uint64 + (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a1->dr)))); /* Case A.1. */ - if (wi::leu_p (diff, min_seg_len_b) + if (must_le (diff, min_seg_len_b) /* Case A.2 and B combined. */ - || (tree_fits_uhwi_p (dr_a2->seg_len))) + || const_seg_len_a2) { - if (tree_fits_uhwi_p (dr_a1->seg_len) - && tree_fits_uhwi_p (dr_a2->seg_len)) - { - wide_int min_len - = wi::umin (wi::to_wide (dr_a1->seg_len) - diff, - wi::to_wide (dr_a2->seg_len)); - new_seg_len = wide_int_to_tree (sizetype, min_len); - } + if (const_seg_len_a1 || const_seg_len_a2) + new_seg_len + = build_int_cstu (sizetype, + lower_bound (seg_len_a1 - diff, + seg_len_a2)); else new_seg_len = size_binop (MINUS_EXPR, dr_a2->seg_len, - wide_int_to_tree (sizetype, diff)); + build_int_cstu (sizetype, diff)); dr_a2->seg_len = new_seg_len; do_remove = true; @@ -1571,22 +1581,19 @@ prune_runtime_alias_test_list (vecseg_len))) + || const_seg_len_a1) { - if (tree_fits_uhwi_p (dr_a1->seg_len) - && tree_fits_uhwi_p (dr_a2->seg_len)) - { - wide_int max_len - = wi::umax (wi::to_wide (dr_a2->seg_len) + diff, - wi::to_wide (dr_a1->seg_len)); - new_seg_len = wide_int_to_tree (sizetype, max_len); - } + if (const_seg_len_a1 && const_seg_len_a2) + new_seg_len + = build_int_cstu (sizetype, + upper_bound (seg_len_a2 + diff, + seg_len_a1)); else new_seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len, - wide_int_to_tree (sizetype, diff)); + build_int_cstu (sizetype, diff)); dr_a1->seg_len = new_seg_len; do_remove = true;