From patchwork Thu Feb 16 23:12:31 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: 9578499 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 A300060209 for ; Thu, 16 Feb 2017 23:14:51 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 9C33828636 for ; Thu, 16 Feb 2017 23:14:51 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 910CE28698; Thu, 16 Feb 2017 23:14:51 +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 3E18928636 for ; Thu, 16 Feb 2017 23:14:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933157AbdBPXOu (ORCPT ); Thu, 16 Feb 2017 18:14:50 -0500 Received: from mail-wr0-f195.google.com ([209.85.128.195]:34564 "EHLO mail-wr0-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933744AbdBPXOt (ORCPT ); Thu, 16 Feb 2017 18:14:49 -0500 Received: by mail-wr0-f195.google.com with SMTP id c4so3668117wrd.1 for ; Thu, 16 Feb 2017 15:14:48 -0800 (PST) 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=U/Y4hVUjYDe7pAH6b42w/ksjDShHpZZo1XedGGQJt2E=; b=ttWQ0gQ2ikvT8Qct5HSceP9+jd1rTnSlTHOrU9oWo5dwTbfvUYbqkreem6HEpBmvYt bMNNt6dDyFqa0gZ9gyPFRnTt5Ekh2B5cV/meqN3h9inR5r09NKe1gVkFBdkbjaNxQ5fo EPumQpHVUlC/31rEbt1dhL7ctjBwttYz0FNcgoKBMmbo8QWdf+yKHFUhySrzG+aGUKXM 647JCHmai1s9w6t+fOo5zm+qbJx9Fdj98fOpkPy67Nse3T8fnmGakfJePO3aThyQV52m wvL3e6nGvgzbX1kdFKhXkeIkycmxIes2M/wy4q+Mx1lXkuJU8FEldLNgtA814ZCVXDOQ bomQ== 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=U/Y4hVUjYDe7pAH6b42w/ksjDShHpZZo1XedGGQJt2E=; b=esO9q/pHeGFTeJrEvzAL5qC4/WAWY48ndfQWyUmvUwqtxZsxYKMzSrCWGWBr4sgMlm 6Vyc5vpywT1X3epAzltAD6j8ZnPfwwoecvX4IK0bEeBu7c0FUlpdsjttYMNJysqwcNh/ 6U0ZAPEjqLRkKKtjA4exOY1C7vnaiNST+q75e7Xs0bXxt8vdOsXtrsGSO4Nvs7bBF2C1 EYllR+/Ots3WWBFB6JnnIaoblUnyPUPAI/19lHgbZYYiUUqv64oyL5VZvpyyrKvS8xWx hFS+f5SBLG2JzfvILyALiEZUlQf+ZDZpndSnlRqtYSKt5Im3sU61kE5NK2y+54XE6a2w RUAw== X-Gm-Message-State: AMke39mmun3z0A2gdIN+FPlfhdZ04LczQZf76hBGWE8ODXjVXjrk7VChqH+bOhhXr02UXQ== X-Received: by 10.223.168.1 with SMTP id l1mr4225695wrc.150.1487286882935; Thu, 16 Feb 2017 15:14:42 -0800 (PST) Received: from localhost.localdomain ([2a02:a03f:82f:a300:5964:5014:4d9b:afe1]) by smtp.gmail.com with ESMTPSA id g6sm2027240wmc.30.2017.02.16.15.14.42 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 16 Feb 2017 15:14:42 -0800 (PST) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Christopher Li , Luc Van Oostenryck Subject: [PATCH 4/4] CSE: improve hashing of non-commutative binops Date: Fri, 17 Feb 2017 00:12:31 +0100 Message-Id: <20170216231231.5781-5-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20170216231231.5781-1-luc.vanoostenryck@gmail.com> References: <20170216231231.5781-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 During CSE equivalent instructions should hash to the same value but we should also try to *not* hash to the same value instructions that cannot be equivalent. For commutative ops this means that the hash function should itself be commutative/symmetrical regarding the exchange of its operands. This is already the case but the current hash function is symmetrical for all binops, not only the commutative ones. Thus expressions like 'a - b' and 'b - a' hash to the same value while it should be the case only when 'a == b'. Fix this by changing the hashing of non-commutative binops so that it is anti-symmetrical regarding the exchange of operands while keeping commutative ones symmetrical. This change have no functional effects (in the sense that it shoudl CSE exactly the same instructiosn as before), it should only improve the efficiency of the hashing+comparing. Note: on the 5000+ test set I'm using, I can't see any significant speedup which is quite normal since most of the functions therein have (much) less instructions than the size of the hash table. The effect of this patch should only be on much bigger functions. Signed-off-by: Luc Van Oostenryck --- cse.c | 26 ++++++++++++++------------ 1 file changed, 14 insertions(+), 12 deletions(-) diff --git a/cse.c b/cse.c index 0d3815c5a..89812afae 100644 --- a/cse.c +++ b/cse.c @@ -51,28 +51,30 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction hash += hashval(insn->src3); /* Fall through */ - /* Binary arithmetic */ - case OP_ADD: case OP_SUB: - case OP_MULU: case OP_MULS: + /* non-commutative binops */ + case OP_SUB: case OP_DIVU: case OP_DIVS: case OP_MODU: case OP_MODS: case OP_SHL: case OP_LSR: case OP_ASR: - case OP_AND: case OP_OR: - - /* Binary logical */ - case OP_XOR: case OP_AND_BOOL: - case OP_OR_BOOL: - - /* Binary comparison */ - case OP_SET_EQ: case OP_SET_NE: case OP_SET_LE: case OP_SET_GE: case OP_SET_LT: case OP_SET_GT: case OP_SET_B: case OP_SET_A: case OP_SET_BE: case OP_SET_AE: + hash -= hashval(insn->src2); + hash += hashval(insn->src1); + break; + + /* commutative binops */ + case OP_SET_EQ: case OP_SET_NE: + case OP_ADD: + case OP_MULU: case OP_MULS: + case OP_AND_BOOL: case OP_OR_BOOL: + case OP_AND: case OP_OR: + case OP_XOR: hash += hashval(insn->src2); /* Fall through */ - + /* Unary */ case OP_NOT: case OP_NEG: hash += hashval(insn->src1);