From patchwork Thu Jan 16 09:41:27 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Kewen.Lin" X-Patchwork-Id: 1224107 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-517499-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=linux.ibm.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha1 header.s=default header.b=kAFoIKI5; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47yzjw063cz9sNx for ; Thu, 16 Jan 2020 20:41:55 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:from:to:cc:references:date:mime-version:in-reply-to :content-type:message-id; q=dns; s=default; b=NKN9/rVD0AXYjWjdgN /+UN6YmN3uaNu5SdkJ2akh/0EXb9ddjvpMDY4l97p2tf0a2sXtF1sGA4mUa3QhsQ poXz26cpsRg+DGg49P3pQieaF2FkRb/hvWWILzQlB1upVKfkDLo8rrqMSxEGxwse V9/Aielaw/dPbOj+ehkTNwKFo= 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 :subject:from:to:cc:references:date:mime-version:in-reply-to :content-type:message-id; s=default; bh=R9YJEVafvt08Zt6D7SNhM+ZB 8RE=; b=kAFoIKI5wtjLVBghhYz/5qtnSeajp9/J9Z3TcSAGbGaaT8Oj08Kf6qze Q4PAsYA/bFHaOwWUCLE195Otp/HCA5LAnV1qhhG61bQaCfd5V9IdE8SwiW7RmIEk cVFXo9axo4Rsja1K1DmI5AXF4VwNuBcnrc75GjwD5icmy37e3II= Received: (qmail 2910 invoked by alias); 16 Jan 2020 09:41:48 -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 2902 invoked by uid 89); 16 Jan 2020 09:41:48 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-21.4 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.1 spammy= X-HELO: mx0a-001b2d01.pphosted.com Received: from mx0b-001b2d01.pphosted.com (HELO mx0a-001b2d01.pphosted.com) (148.163.158.5) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 16 Jan 2020 09:41:37 +0000 Received: from pps.filterd (m0098416.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.42/8.16.0.42) with SMTP id 00G9bvVY106699 for ; Thu, 16 Jan 2020 04:41:36 -0500 Received: from e06smtp04.uk.ibm.com (e06smtp04.uk.ibm.com [195.75.94.100]) by mx0b-001b2d01.pphosted.com with ESMTP id 2xh7h9n788-1 (version=TLSv1.2 cipher=AES256-GCM-SHA384 bits=256 verify=NOT) for ; Thu, 16 Jan 2020 04:41:35 -0500 Received: from localhost by e06smtp04.uk.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Thu, 16 Jan 2020 09:41:34 -0000 Received: from b06avi18626390.portsmouth.uk.ibm.com (9.149.26.192) by e06smtp04.uk.ibm.com (192.168.101.134) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; (version=TLSv1/SSLv3 cipher=AES256-GCM-SHA384 bits=256/256) Thu, 16 Jan 2020 09:41:32 -0000 Received: from d06av21.portsmouth.uk.ibm.com (d06av21.portsmouth.uk.ibm.com [9.149.105.232]) by b06avi18626390.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 00G9egPL37749132 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 16 Jan 2020 09:40:42 GMT Received: from d06av21.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 36FAE52051; Thu, 16 Jan 2020 09:41:31 +0000 (GMT) Received: from kewenlins-mbp.cn.ibm.com (unknown [9.200.147.222]) by d06av21.portsmouth.uk.ibm.com (Postfix) with ESMTP id 1195A52054; Thu, 16 Jan 2020 09:41:28 +0000 (GMT) Subject: [PATCH 3/4 GCC11] IVOPTs Consider cost_step on different forms during unrolling From: "Kewen.Lin" To: GCC Patches Cc: Segher Boessenkool , Bill Schmidt , "bin.cheng" , Richard Guenther References: Date: Thu, 16 Jan 2020 17:41:27 +0800 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:68.0) Gecko/20100101 Thunderbird/68.2.2 MIME-Version: 1.0 In-Reply-To: x-cbid: 20011609-0016-0000-0000-000002DDCD90 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 20011609-0017-0000-0000-000033406474 Message-Id: X-IsSubscribed: yes gcc/ChangeLog 2020-01-16 Kewen Lin * tree-ssa-loop-ivopts.c (struct iv_group): New field dform_p. (struct iv_cand): New field dform_p. (struct ivopts_data): New field mark_dform_p. (record_group): Initialize dform_p. (mark_dform_groups): New function. (find_interesting_uses): Call mark_dform_groups. (add_candidate_1): Update dform_p if derived from dform_p group. (determine_iv_cost): Increase cost by considering unroll factor. (tree_ssa_iv_optimize_loop): Call estimate_unroll_factor, update mark_dform_p. gcc/tree-ssa-loop-ivopts.c | 84 +++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 83 insertions(+), 1 deletion(-) diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index ab52cbe..a0d29bb 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -429,6 +429,8 @@ struct iv_group struct iv_cand *selected; /* To indicate this is a doloop use group. */ bool doloop_p; + /* To indicate this group is D-form preferred. */ + bool dform_p; /* Uses in the group. */ vec vuses; }; @@ -470,6 +472,7 @@ struct iv_cand struct iv *orig_iv; /* The original iv if this cand is added from biv with smaller type. */ bool doloop_p; /* Whether this is a doloop candidate. */ + bool dform_p; /* Derived from one D-form preferred group. */ }; /* Hashtable entry for common candidate derived from iv uses. */ @@ -650,6 +653,10 @@ struct ivopts_data /* Whether the loop has doloop comparison use. */ bool doloop_use_p; + + /* Whether the loop is likely to unroll and need to check and mark + D-form group for better step cost modeling. */ + bool mark_dform_p; }; /* An assignment of iv candidates to uses. */ @@ -1575,6 +1582,7 @@ record_group (struct ivopts_data *data, enum use_type type) group->related_cands = BITMAP_ALLOC (NULL); group->vuses.create (1); group->doloop_p = false; + group->dform_p = false; data->vgroups.safe_push (group); return group; @@ -2724,6 +2732,59 @@ split_address_groups (struct ivopts_data *data) } } +/* Go through all address type groups, check and mark D-form preferred. */ +static void +mark_dform_groups (struct ivopts_data *data) +{ + if (!data->mark_dform_p) + return; + + class loop *loop = data->current_loop; + bool dump_details = (dump_file && (dump_flags & TDF_DETAILS)); + for (unsigned i = 0; i < data->vgroups.length (); i++) + { + struct iv_group *group = data->vgroups[i]; + if (address_p (group->type)) + { + bool found = true; + for (unsigned j = 0; j < group->vuses.length (); j++) + { + struct iv_use *use = group->vuses[j]; + gcc_assert (use->mem_type); + /* Ensure the step fit into D-form field. */ + if (TREE_CODE (use->iv->step) != INTEGER_CST + || !tree_fits_shwi_p (use->iv->step)) + { + found = false; + if (dump_details) + fprintf (dump_file, + " Group use %u.%u doesn't" + "have constant step for D-form.\n", + i, j); + break; + } + bool is_store + = TREE_CODE (gimple_assign_lhs (use->stmt)) == SSA_NAME; + if (!targetm.stride_dform_valid_p (TYPE_MODE (use->mem_type), + tree_to_shwi (use->iv->step), + TYPE_UNSIGNED (use->mem_type), + is_store, loop->estimated_uf)) + { + found = false; + if (dump_details) + fprintf (dump_file, + " Group use %u.%u isn't" + "suitable for D-form.\n", + i, j); + break; + } + } + if (found) + group->dform_p = true; + } + } +} + /* Finds uses of the induction variables that are interesting. */ static void @@ -2755,6 +2816,8 @@ find_interesting_uses (struct ivopts_data *data) split_address_groups (data); + mark_dform_groups (data); + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "\n:\n"); @@ -3137,6 +3200,7 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important, cand->important = important; cand->incremented_at = incremented_at; cand->doloop_p = doloop; + cand->dform_p = false; data->vcands.safe_push (cand); if (!poly_int_tree_p (step)) @@ -3173,7 +3237,11 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important, /* Relate candidate to the group for which it is added. */ if (use) - bitmap_set_bit (data->vgroups[use->group_id]->related_cands, i); + { + bitmap_set_bit (data->vgroups[use->group_id]->related_cands, i); + if (data->vgroups[use->group_id]->dform_p) + cand->dform_p = true; + } return cand; } @@ -5867,6 +5935,10 @@ determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand) cost_step = add_cost (data->speed, TYPE_MODE (TREE_TYPE (base))); cost = cost_step + adjust_setup_cost (data, cost_base.cost); + /* Consider the stride update cost during unrolling. */ + if (!cand->dform_p) + cost += (data->current_loop->estimated_uf - 1) * cost_step; + /* Prefer the original ivs unless we may gain something by replacing it. The reason is to make debugging simpler; so this is not relevant for artificial ivs created by other optimization passes. */ @@ -7953,6 +8025,7 @@ tree_ssa_iv_optimize_loop (struct ivopts_data *data, class loop *loop, data->current_loop = loop; data->loop_loc = find_loop_location (loop).get_location_t (); data->speed = optimize_loop_for_speed_p (loop); + data->mark_dform_p = false; if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -7984,6 +8057,15 @@ tree_ssa_iv_optimize_loop (struct ivopts_data *data, class loop *loop, if (!find_induction_variables (data)) goto finish; + if (targetm.stride_dform_valid_p && exit) + { + tree_niter_desc *desc = niter_for_exit (data, exit); + estimate_unroll_factor (loop, desc); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "estimated_uf:%u\n", loop->estimated_uf); + data->mark_dform_p = loop->estimated_uf > 1; + } + /* Finds interesting uses (item 1). */ find_interesting_uses (data); if (data->vgroups.length () > MAX_CONSIDERED_GROUPS)