From patchwork Mon Jul 21 09:46:24 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Bin.Cheng" X-Patchwork-Id: 372016 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)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 414F014011E for ; Mon, 21 Jul 2014 19:46:43 +1000 (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=q+tAuuO2MkwCoEhvPE oNsKds9ZlUNqqfKizIkfT4MBmAtIaZLnw0RoJ/9c+sAn/UCG2oB+ej/Ax4L+J4NZ 8qEX3d0hhkAOnT8LxhTTDEY7USP7lFYcfI4fvzUWKG5s5sB4reYSk0laoCrM9FFG mSfUnMNJZ2EauqX0OklW9dnhI= 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=BmQOsO/gRgyyPv8egjCe+XPI KGU=; b=H9PtkVip+/YrSbSEOxZjKRSahY7h8ELEPh2tdUpQkR7y53zchI0x6Voh Ry7y/boTgJ6J3espQABsXWCT+QZLHdwSMN9jbi4iSgcCLiaRVeGw2kSNeUGAUO+y dUZB+P0W10v9YPTkNJJQd6//Qi49rtRtuDhyyveonXwlldGiHA8= Received: (qmail 16790 invoked by alias); 21 Jul 2014 09:46:34 -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 16728 invoked by uid 89); 21 Jul 2014 09:46:31 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.2 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-qg0-f46.google.com Received: from mail-qg0-f46.google.com (HELO mail-qg0-f46.google.com) (209.85.192.46) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Mon, 21 Jul 2014 09:46:26 +0000 Received: by mail-qg0-f46.google.com with SMTP id z60so5091144qgd.5 for ; Mon, 21 Jul 2014 02:46:24 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.140.106.225 with SMTP id e88mr37145196qgf.20.1405935984557; Mon, 21 Jul 2014 02:46:24 -0700 (PDT) Received: by 10.140.49.111 with HTTP; Mon, 21 Jul 2014 02:46:24 -0700 (PDT) In-Reply-To: <002a01cfa19e$8752d0d0$95f87270$@arm.com> References: <002a01cfa19e$8752d0d0$95f87270$@arm.com> Date: Mon, 21 Jul 2014 10:46:24 +0100 Message-ID: Subject: Fwd: [PATCH 1/3]Improve induction variable elimination From: "Bin.Cheng" To: Zdenek Dvorak Cc: gcc-patches List X-IsSubscribed: yes Hi, forward to Zdenek for the review. Thanks, bin ---------- Forwarded message ---------- From: Bin Cheng Date: Thu, Jul 17, 2014 at 10:07 AM Subject: [PATCH 1/3]Improve induction variable elimination To: gcc-patches@gcc.gnu.org Hi, This is a series of three patches improving induction variable elimination. Currently GCC only eliminates iv for very specific case when the loop's latch could run zero times, i.e., when may_be_zero field of loop niter information evaluates to true. In fact, it's so specific that iv_elimination_compare_lt rarely succeeds during either GCC bootstrap or spec2000/spec2006 compilation. Though intrusive data shows these patches don't help iv elimination that much for GCC bootstrap, they do capture 5%~15% more eliminations for compiling spec2000/2006. Detailed numbers are like: 2k/int 2k/fp 2k6/int 2k6/fp improve ~9.6% ~4.8% ~5.5% ~14.4% All patches pass bootstrap and regression test on x86_64/x86. I will bootstrap and test them on aarch64/arm platforms too. The first patch turns to tree operand_equal_p to check the number of iterations in iv_elimination_lt. Though I think this change isn't necessary for current code, it's needed if we further relax iv elimination for cases in which sign/unsigned conversion is involved. Thanks, bin 2014-07-17 Bin Cheng * tree-ssa-loop-ivopts.c (iv_elimination_compare_lt): Check number of iteration using tree comparison. Index: gcc/tree-ssa-loop-ivopts.c =================================================================== --- gcc/tree-ssa-loop-ivopts.c (revision 212387) +++ gcc/tree-ssa-loop-ivopts.c (working copy) @@ -4605,7 +4605,7 @@ iv_elimination_compare_lt (struct ivopts_data *dat struct tree_niter_desc *niter) { tree cand_type, a, b, mbz, nit_type = TREE_TYPE (niter->niter), offset; - struct aff_tree nit, tmpa, tmpb; + struct aff_tree nit, tmp1, tmpa, tmpb; enum tree_code comp; HOST_WIDE_INT step; @@ -4661,15 +4661,19 @@ iv_elimination_compare_lt (struct ivopts_data *dat return false; /* Expected number of iterations is B - A - 1. Check that it matches - the actual number, i.e., that B - A - NITER = 1. */ + the actual number, i.e., that B - A = NITER + 1. */ tree_to_aff_combination (niter->niter, nit_type, &nit); - tree_to_aff_combination (fold_convert (nit_type, a), nit_type, &tmpa); - tree_to_aff_combination (fold_convert (nit_type, b), nit_type, &tmpb); - aff_combination_scale (&nit, -1); - aff_combination_scale (&tmpa, -1); - aff_combination_add (&tmpb, &tmpa); - aff_combination_add (&tmpb, &nit); - if (tmpb.n != 0 || tmpb.offset != 1) + aff_combination_const (&tmp1, nit_type, 1); + tree_to_aff_combination (b, TREE_TYPE (b), &tmpb); + aff_combination_add (&nit, &tmp1); + if (a != integer_zero_node) + { + tree_to_aff_combination (a, TREE_TYPE (b), &tmpa); + aff_combination_scale (&tmpa, -1); + aff_combination_add (&tmpb, &tmpa); + } + if (!operand_equal_p (aff_combination_to_tree (&nit), + aff_combination_to_tree (&tmpb), 0)) return false; /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not