From patchwork Wed Jul 25 07:27:33 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Bonzini X-Patchwork-Id: 173115 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 BB9B92C0085 for ; Wed, 25 Jul 2012 17:28:00 +1000 (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=1343806082; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC: Subject:References:In-Reply-To:Content-Type: Content-Transfer-Encoding:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=/qxYBqvkOu9KOxZZnbmf18ES7Cs=; b=b+V71dzndSo3WnH ruao300DebH3mAB5+T0WeOQduug95dP+X8uiMfdY0APgiClMbAkFFBjaq1QDyh2K WApQ1d85gfrJ42PKYIe0Odu/2FIUcelDCypjvrYCbomz9ZV6uE91AqkwrrqWmba7 6XFtYJ0IZv7mZwIermNtDHTc2OSQ= 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:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:References:In-Reply-To:Content-Type:Content-Transfer-Encoding:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=ZP2XOP50aA0z28Dsaep4IQ3/QwtIorcf27WK+p2z9DnwJ2OWb6xKXSCsL45ljo v5Mp3qrfUsbTCaaInH4jxqLUcmL7+L76jvvGmXdxSqeVg+Qi3jspw6fDTyoSZ0lf DT96ULOrCBK8MMKeAg8jMEdhcpjUc+4cBzsFxQaO8Lz/8=; Received: (qmail 28446 invoked by alias); 25 Jul 2012 07:27:55 -0000 Received: (qmail 28431 invoked by uid 22791); 25 Jul 2012 07:27:53 -0000 X-SWARE-Spam-Status: No, hits=-5.0 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, KHOP_RCVD_TRUST, KHOP_THREADED, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE X-Spam-Check-By: sourceware.org Received: from mail-we0-f175.google.com (HELO mail-we0-f175.google.com) (74.125.82.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 25 Jul 2012 07:27:39 +0000 Received: by weyr6 with SMTP id r6so354816wey.20 for ; Wed, 25 Jul 2012 00:27:37 -0700 (PDT) Received: by 10.216.123.69 with SMTP id u47mr7221751weh.89.1343201257559; Wed, 25 Jul 2012 00:27:37 -0700 (PDT) Received: from yakj.usersys.redhat.com (93-34-189-113.ip51.fastwebnet.it. [93.34.189.113]) by mx.google.com with ESMTPS id b7sm1960752wiz.9.2012.07.25.00.27.35 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 25 Jul 2012 00:27:36 -0700 (PDT) Message-ID: <500F9FE5.5040302@gnu.org> Date: Wed, 25 Jul 2012 09:27:33 +0200 From: Paolo Bonzini User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:13.0) Gecko/20120615 Thunderbird/13.0.1 MIME-Version: 1.0 To: Sandra Loosemore CC: gcc-patches@gcc.gnu.org, Andrew Jenner Subject: Re: [PATCH] Detect loops in find_comparison_args References: <500F02E3.5080804@codesourcery.com> In-Reply-To: <500F02E3.5080804@codesourcery.com> 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 Il 24/07/2012 22:17, Sandra Loosemore ha scritto: > I was looking to see what needs to be done to un-stick this previously > submitted patch: > > http://gcc.gnu.org/ml/gcc-patches/2012-05/msg01419.html > > Paolo's suggestion was to re-write this to use a "tortoise-and-hare" > algorithm to detect the circularity, rather than Andrew's solution of > using a pointer_set to keep track of already-visited states. > > Having spent a couple hours scratching my head over how to do the > suggested re-write, I'm thinking that Andrew's proposed patch is really > the better solution after all. This isn't a linked list we're > traversing, it's an iterative computation, This doesn't really matter, because the tortoise-and-hare algorithm _is_ really about iterative computation (following a linked list uses "x = x->next" as the iterative computation). However... > so doing the > tortoise-and-hare thing either requires a lot of extra recomputation > even in the normal case where it terminates quickly, or building some > data structures to track already-visited states. And, if we're going to > build data structures, why not use ones we already have a convenient > library for? What else are such libraries for but to consolidate common > code and make it easier to express such idioms? IMO, that's a > lighter-weight solution than further complicating this code, and I feel > much more confident that it'll squash an entire class of lurking bugs > without introducing new ones. ... it's a lot simpler than this: I didn't notice that the check is within a nested loop, so you cannot simply treat the outer "while" as the function being iterated. This indeed makes it more practical to use a pointer_set to track the visited values. What I'm worried about is the extra cost of malloc-ing and free-ing the pointer set. Perhaps you can skip the pointer set creation in the common case where find_comparison_args does not iterate? Something like this: It will be more expensive in the rare case of a cycle, but that's _really_ rare if it took 20-odd years to find it. Paolo > Paolo, will you reconsider this? Anyone else care to join the fray? > > -Sandra > > Index: cse.c =================================================================== --- cse.c (revisione 189837) +++ cse.c (copia locale) @@ -2897,6 +2897,8 @@ find_comparison_args (enum rtx_code code enum machine_mode *pmode1, enum machine_mode *pmode2) { rtx arg1, arg2; + rtx x = NULL; + int i = 0; arg1 = *parg1, arg2 = *parg2; @@ -2905,15 +2907,24 @@ find_comparison_args (enum rtx_code code while (arg2 == CONST0_RTX (GET_MODE (arg1))) { /* Set nonzero when we find something of interest. */ - rtx x = 0; int reverse_code = 0; struct table_elt *p = 0; + /* Before starting the second iteration, set up the pointer_set + we use to avoid loops. Most of the time (?) we do not iterate + at all, and we skip creating the set. */ + if (++i >= 2) + { + if (!visited) + visited = pointer_set_create (); + pointer_set_insert (visited, x); + } + /* If arg1 is a COMPARE, extract the comparison arguments from it. On machines with CC0, this is the only case that can occur, since fold_rtx will return the COMPARE or item being compared with zero when given CC0. */ + x = NULL; if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx) x = arg1; @@ -2985,10 +2996,8 @@ find_comparison_args (enum rtx_code code if (! exp_equiv_p (p->exp, p->exp, 1, false)) continue; - /* If it's the same comparison we're already looking at, skip it. */ - if (COMPARISON_P (p->exp) - && XEXP (p->exp, 0) == arg1 - && XEXP (p->exp, 1) == arg2) + /* If it's a comparison we've used before, skip it. */ + if (visited && pointer_set_contains (visited, p->exp)) continue; if (GET_CODE (p->exp) == COMPARE @@ -3061,6 +3070,11 @@ find_comparison_args (enum rtx_code code } else if (COMPARISON_P (x)) code = GET_CODE (x); + + /* If it's the same comparison we're already looking at, stop. */ + if (XEXP (x, 0) == arg1 && XEXP (x, 1) == arg2) + break; + arg1 = XEXP (x, 0), arg2 = XEXP (x, 1); } @@ -3068,6 +3082,8 @@ find_comparison_args (enum rtx_code code because fold_rtx might produce const_int, and then it's too late. */ *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2); *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0); + if (visited) + pointer_set_destroy (visited); return code; }