From patchwork Wed Apr 12 12:59:12 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 9677491 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id DBE1B60383 for ; Wed, 12 Apr 2017 13:01:34 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id CE78828662 for ; Wed, 12 Apr 2017 13:01:34 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id C3A8F2866C; Wed, 12 Apr 2017 13:01:34 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.3 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_HI, RCVD_IN_SORBS_SPAM, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B73C628662 for ; Wed, 12 Apr 2017 13:01:33 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753720AbdDLNBd (ORCPT ); Wed, 12 Apr 2017 09:01:33 -0400 Received: from mail-wm0-f65.google.com ([74.125.82.65]:33251 "EHLO mail-wm0-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753708AbdDLNBb (ORCPT ); Wed, 12 Apr 2017 09:01:31 -0400 Received: by mail-wm0-f65.google.com with SMTP id o81so6281265wmb.0 for ; Wed, 12 Apr 2017 06:01:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=ytG1LZ2eDGv2FNpFX2a5rrm7b5VhU5OLMA5F+8WyaCo=; b=FaQZho2uW45cOpr3AvvjRqe+Xcgy8d8hJUpuC2iTp2bZ0sj3QO6rW2afwAQIROkj7z 4X/XMxWg1+I/h38QPKjK+nGzWEKILAkUddNlo1ptJF2D8szh2R+BYG7u8nR4aZLbDB+C I67PFnfEAWTelXS5uOmmDHCZzIu+vYh4LrDWg6MJzB8wT0wP6nPODRZprDD4iftJKqJz r7xvfkNwtvz2HPuK2V3n9/6c7pV3W5q8p1hgWEUnRcWErAQR7bC+94vwLfgGlHmeLPQo il72K9eDXC4X3n/3IWxAHVLyFJVgX18psl3X3o0EhrUj1XVoQU7Zgiqya/R6fNhzyQPL bmqQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=ytG1LZ2eDGv2FNpFX2a5rrm7b5VhU5OLMA5F+8WyaCo=; b=HcG8aQnL9J/OxIVNU2uSAdn9XaVK1Oev7myMFQs6IYrpV77NwMJ3KzbfPukzfHfjpw dBovKB2plT4cEdPRfPE7EY8OlnaW5b9SMwAYAWT9lU0ZR933TfbTZhyLWVXSgRK79ttq 9hMQlktTrriS7WM1oxQEfzbgCNoDR3M7nT9U+aGF1Oc1tk/gLk7XgsgMxnenfO+7IuRG A5wFM83UrozFRxIGTflXGl1P6OvJmW8+CpbnIHI3mLj5GsGpK+Tte1ULmKaPToe3g+CS UuCs3dItC/eHqQzkQGUTl6J34ZJrn5WpGDsGntvuohXbj72Xy16foepGdCPx3e4ncjk4 sfJw== X-Gm-Message-State: AN3rC/4ro/AQW3DB6hapwadL9K+35Wbiz2L0mTKZmE1R/vW3OmSwfpWL tBo5f6LRfC9t0Q== X-Received: by 10.28.176.5 with SMTP id z5mr5537103wme.3.1492002090290; Wed, 12 Apr 2017 06:01:30 -0700 (PDT) Received: from localhost.localdomain ([2a02:a03f:8b2:dc00:6c54:829e:388a:2472]) by smtp.gmail.com with ESMTPSA id o22sm25391467wro.45.2017.04.12.06.01.27 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 12 Apr 2017 06:01:29 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Christopher Li , Luc Van Oostenryck Subject: [PATCH 2/2] CSE: extend canonical_order() Date: Wed, 12 Apr 2017 14:59:12 +0200 Message-Id: <20170412125912.46641-3-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170412125912.46641-1-luc.vanoostenryck@gmail.com> References: <20170412125912.46641-1-luc.vanoostenryck@gmail.com> Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Impose an almost-total order between pseudos. This creates more oppportunities for CSE and make simplification slightly easier too. Now the canonical order is: REG > PHI > ARG > SYM > VAL > VOID and REGS, PHIs and ARGs are ordered following their '->nr' field. This order continues to put values at RHS and previous results at LHS while still being quite cheap to check. Signed-off-by: Luc Van Oostenryck --- linearize.h | 4 ++-- simplify.c | 29 +++++++++++++++++++++-------- validation/call-inlined.c | 2 +- validation/optim/cse-dual-cmpeq.c | 1 - 4 files changed, 24 insertions(+), 12 deletions(-) diff --git a/linearize.h b/linearize.h index 6f4298f33..24cbcf94d 100644 --- a/linearize.h +++ b/linearize.h @@ -22,11 +22,11 @@ DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user); enum pseudo_type { PSEUDO_VOID, - PSEUDO_REG, - PSEUDO_SYM, PSEUDO_VAL, + PSEUDO_SYM, PSEUDO_ARG, PSEUDO_PHI, + PSEUDO_REG, }; struct pseudo { diff --git a/simplify.c b/simplify.c index 5e3d57470..6d4ba4d69 100644 --- a/simplify.c +++ b/simplify.c @@ -709,16 +709,29 @@ static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instr remove_usage(p2, pp2); } +/* + * Test if the operands are in canonical order: + * REG > PHI > ARG > SYM > VAL > VOID + * %arg2 > %arg1, %r2 > %r1, %phi2 > %phi1 + */ static int canonical_order(pseudo_t p1, pseudo_t p2) { - /* symbol/constants on the right */ - if (p1->type == PSEUDO_VAL) - return p2->type == PSEUDO_VAL; - - if (p1->type == PSEUDO_SYM) - return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL; - - return 1; + int t1 = p1->type; + int t2 = p2->type; + + switch (t1) { + case PSEUDO_REG: + case PSEUDO_PHI: + case PSEUDO_ARG: + if (t1 == t2) + return p1->nr >= p2->nr; + /* fall-through */ + case PSEUDO_SYM: + case PSEUDO_VAL: + case PSEUDO_VOID: + default: + return t1 >= t2; + } } static int canonicalize_commutative(struct instruction *insn) diff --git a/validation/call-inlined.c b/validation/call-inlined.c index b907ded60..80059f489 100644 --- a/validation/call-inlined.c +++ b/validation/call-inlined.c @@ -25,7 +25,7 @@ const char *qus(void) { return lstrip(messg); } foo: .L0: - add.32 %r3 <- %arg1, %arg2 + add.32 %r3 <- %arg2, %arg1 add.32 %r5 <- %r3, $1 ret.32 %r5 diff --git a/validation/optim/cse-dual-cmpeq.c b/validation/optim/cse-dual-cmpeq.c index 45ceee12d..aade6e989 100644 --- a/validation/optim/cse-dual-cmpeq.c +++ b/validation/optim/cse-dual-cmpeq.c @@ -18,7 +18,6 @@ static int engtge(int a, int b) { return (a > b) == !(b >= a); } * check-name: cse-dual-cmpeq * check-command: test-linearize $file * check-output-ignore - * check-known-to-fail * * check-output-excludes: set[gl][et]\\. * check-output-excludes: seteq\\.