From patchwork Mon Oct 23 17:25:45 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 116807 Delivered-To: patch@linaro.org Received: by 10.140.22.164 with SMTP id 33csp4890399qgn; Mon, 23 Oct 2017 10:26:06 -0700 (PDT) X-Received: by 10.99.111.65 with SMTP id k62mr12083595pgc.56.1508779566273; Mon, 23 Oct 2017 10:26:06 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1508779566; cv=none; d=google.com; s=arc-20160816; b=XurvC1hkH0eO08ScbZG7Ac+Hjb2ixhG8Rlv9+YV1WQSld5gKlQaidVAKCmEfbNDa/K MNCXycNS6e/tPY8HRJE9nk91pU4PhD6bvoRAtvl/cMwo5ksgqe5F36ZhuKu+kLA55Qju ywEXPAQztD7wk/1I2I5hKhYeyMQwLDRH1vpdw/LrtMTpksYAJ+YsJsZR9cO9rF5W2VoY aAjl9BzavW3E3rAWGPv1vHUYvdA/TRrn9VJM45gNEf6rgx9cvutUS509VU9Y7LIDooub ShBXqOIGyDj6KWBViMGE123M5V9pcG5Wrowy/Yjhl5lus3VqVj+NJVaBNbwMFv2lLUXY wlMQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=mime-version:user-agent:message-id:in-reply-to:date:references :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=Cvp2KEVyb3jPdrC9TZI99NwZwEm0hBwuMO8lIdAsEnY=; b=FR6RIZFRaLxh6K9npAJNPvcgzOcmDCQ1Z0Ccgo1k1wth1rMJvh5kmjXZKH6bpfgtgy FCnT4rSCvyGmzhHK4L/ESE3gl/xQ6ANOO73Sb2zRIJKY0Fmu4oMpmM8YPZjf52RcbYwc R74hdHgWb977pIwIIoX/7lq2EK58j2QWTsBETQuv/3XzdHLZeBcNj8FDOrjAb92CvW9Z X5CNPD1ZEDNNLLBJVtUadvCjpCIc5FeCCQCPpy2VBAgHE+r1Ppb0DFCnmgeiaKJ48oYR MAOH9XhKmznrO8yZBf3Y7JSV6ZZKjwYDXmwuzRUVpFv+3tZqi1Ql6RZ9rZ/ABQZAWe2A 3NDw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=oqeqbNhT; spf=pass (google.com: domain of gcc-patches-return-464838-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-464838-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 b64si5633539pfl.505.2017.10.23.10.26.06 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 23 Oct 2017 10:26:06 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-464838-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=oqeqbNhT; spf=pass (google.com: domain of gcc-patches-return-464838-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-464838-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:references:date:in-reply-to:message-id:mime-version :content-type; q=dns; s=default; b=VgP4tV66Y59mrDzTOjrRWQdhgUPFW 6jfRhxbgjMDYdKQzoDrsbka4MkAlIDkp/iDYn8V+I0P69ZeShxravezx7q50MHRM NmuHF2SdLlEC5xYQhjzFjBBtOiS7b0mCxiB15pUdqm9zRW0hVWPAzQ4fv2I73tQH ASZqDdgtvo/M1Y= 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:references:date:in-reply-to:message-id:mime-version :content-type; s=default; bh=uayHEWFfGuJg0WaWiyhFC7EnaxM=; b=oqe qbNhT2ypG/tY0rBtmb19iSOEc0I9CLzdOaiEnZLR0KQaVCQTx6q4y/cjcQsq8ott ipwRBNjfKqmYxmtIaCFsc56b5wSw3ITjw/FsVEqekMzDmNT4YmVx71Op6HpgWHjg AkJ83vfXN29nn4Opx9PTomExePh8nXEZqMpMnPf4= 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-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 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 18:25:45 +0100 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 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;