From patchwork Tue Feb 28 15:10:22 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ulrich Weigand X-Patchwork-Id: 143470 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]) by ozlabs.org (Postfix) with SMTP id 1A4F4B6EEC for ; Wed, 29 Feb 2012 02:10:54 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1331046655; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Received:Message-Id:Received:Subject:To:Date: From:Cc:In-Reply-To:MIME-Version:Content-Type: Content-Transfer-Encoding:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=oceuNIkMv/AtubTB6HI27ofJYcM=; b=tPV9utMlX2Pzo6T +UAmWT58BGA79+jP60SwFN5VSxz+0igASHFaJ8IwDNXl93AiUxFOxUrfKL77+nNI ysVXrYc7Oig+EfuqAWgnrvn07TS8F2OzMKtvdIHrFLqhaRf5xJm4X3FStz8Osdsx jQNahJoJLWGOQ+/SRamY3/LO672I= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Received:Received:Received:Message-Id:Received:Subject:To:Date:From:Cc:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding:x-cbid:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=eibRt3qFXklmYyUyDw2aCi8aDU8G1Ux2sDzySHg+TiLPwoH1u0hbLVjsE/CwOM 9RJUMZpcosBmJN0S2+5TVhyM+JOShvRdBjp3vEmZQ+cyGT/4Hxr6CJOHyDlHXWDW BTls4hjyQ8W/10B9oNdXP6VZGyhB4uWCmDoxX6jps7IUA=; Received: (qmail 7327 invoked by alias); 28 Feb 2012 15:10:46 -0000 Received: (qmail 7302 invoked by uid 22791); 28 Feb 2012 15:10:44 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, MSGID_FROM_MTA_HEADER, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from e06smtp17.uk.ibm.com (HELO e06smtp17.uk.ibm.com) (195.75.94.113) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 28 Feb 2012 15:10:29 +0000 Received: from /spool/local by e06smtp17.uk.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 28 Feb 2012 15:10:27 -0000 Received: from d06nrmr1806.portsmouth.uk.ibm.com (9.149.39.193) by e06smtp17.uk.ibm.com (192.168.101.147) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Tue, 28 Feb 2012 15:10:24 -0000 Received: from d06av02.portsmouth.uk.ibm.com (d06av02.portsmouth.uk.ibm.com [9.149.37.228]) by d06nrmr1806.portsmouth.uk.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id q1SFANOP2351108; Tue, 28 Feb 2012 15:10:23 GMT Received: from d06av02.portsmouth.uk.ibm.com (loopback [127.0.0.1]) by d06av02.portsmouth.uk.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id q1SFANa5022434; Tue, 28 Feb 2012 08:10:23 -0700 Received: from tuxmaker.boeblingen.de.ibm.com (tuxmaker.boeblingen.de.ibm.com [9.152.85.9]) by d06av02.portsmouth.uk.ibm.com (8.14.4/8.13.1/NCO v10.0 AVin) with SMTP id q1SFAMDY022388; Tue, 28 Feb 2012 08:10:22 -0700 Message-Id: <201202281510.q1SFAMDY022388@d06av02.portsmouth.uk.ibm.com> Received: by tuxmaker.boeblingen.de.ibm.com (sSMTP sendmail emulation); Tue, 28 Feb 2012 16:10:22 +0100 Subject: [WIP PATCH] Re: Inefficient end-of-loop value computation - missed optimization somewhere? To: richard.guenther@gmail.com (Richard Guenther), gcc-patches@gcc.gnu.org Date: Tue, 28 Feb 2012 16:10:22 +0100 (CET) From: "Ulrich Weigand" Cc: gcc@gcc.gnu.org In-Reply-To: from "Richard Guenther" at Feb 21, 2012 10:27:21 AM MIME-Version: 1.0 x-cbid: 12022815-0542-0000-0000-0000011CAB1A 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 Richard Guenther wrote: > On Mon, Feb 20, 2012 at 11:19 PM, Ulrich Weigand wrote: > > we've noticed that the loop optimizer sometimes inserts weirdly > > inefficient code to compute the value of an induction variable > > at the end of the loop. [snip] > The issue is that (start + 1) + 1 * (int) ... is computed using signed > integer arithmetic which may invoke undefined behavior when it wraps. > Thus we cannot re-associate it. I suppose if you'd arrange the code > to do the arithmetic in unsigned and only cast the result back to the > desired type we might fold it ... I'm not completely sure I've got the correct place for the conversions, but using the patch below does indeed fix the inefficient code. I'll still need to do proper testing and benchmarking, but I thought I'd post the patch anyway just as a heads-up ... Does this look reasonable to you? Thanks, Ulrich ChangeLog: * tree-scalar-evolution.c (compute_overall_effect_of_inner_loop): Perform chrec_apply computation in an unsigned type. Index: gcc/tree-scalar-evolution.c =================================================================== --- gcc/tree-scalar-evolution.c (revision 184439) +++ gcc/tree-scalar-evolution.c (working copy) @@ -474,11 +474,18 @@ return chrec_dont_know; else { + tree type = TREE_TYPE (evolution_fn); + tree utype = unsigned_type_for (type); tree res; /* evolution_fn is the evolution function in LOOP. Get - its value in the nb_iter-th iteration. */ - res = chrec_apply (inner_loop->num, evolution_fn, nb_iter); + its value in the nb_iter-th iteration. Since the + number of iterations is always unsigned, we perform + the computation in an unsigned type to allow for + improved simplification of subexpressions. */ + res = chrec_convert (utype, evolution_fn, NULL); + res = chrec_apply (inner_loop->num, res, nb_iter); + res = chrec_convert (type, res, NULL); if (chrec_contains_symbols_defined_in_loop (res, loop->num)) res = instantiate_parameters (loop, res);