From patchwork Tue Mar 19 17:13:51 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marc Glisse X-Patchwork-Id: 229147 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 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 0D76C2C0097 for ; Wed, 20 Mar 2013 04:14:10 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= dkim1; b=wQqGdaDqbNYOCH/8gObsUZlyvwfK/728izEM/q7sw5P3s4NS3kGamCz G2/SRnuzrmlVLTeDk3s334Gf6g4gKYQhC1BhdtYjFnd+qOWoe82nrrJ6ojlBJFgB clguHznJTZknIUIlsRu5wbsdGogZWepdiLYNK6kT5qLYTDXLV92o= DKIM-Signature: v=1; a=rsa-sha1; c=simple; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s=dkim1; bh=vb/CfESA4Bvr9Iu3xBQ32JEA7xo=; b=G2iylZpWoOJS5bXPwvsIO6oLTQZd xBTgVNFqXlkksfwcIl0xFKotk27s5+ieMys6sOjdVgCqPAsEY7bLUl0tLpgzs9Dh 61rX5OfUaz4y2R7bYZw77iSIqa9ek+KDjJn+mwncEjtvJZNO4Ah33+YmGFQ3jNsl 71EZLQMp4s/kuuA= Received: (qmail 5508 invoked by alias); 19 Mar 2013 17:14:05 -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 5449 invoked by uid 89); 19 Mar 2013 17:13:57 -0000 X-Spam-Sware-Status: No, score=-8.9 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD autolearn=ham version=3.3.1 Received: from mail2-relais-roc.national.inria.fr (HELO mail2-relais-roc.national.inria.fr) (192.134.164.83) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Tue, 19 Mar 2013 17:13:53 +0000 Received: from stedding.saclay.inria.fr ([193.55.250.194]) by mail2-relais-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES128-SHA; 19 Mar 2013 18:13:51 +0100 Received: from glisse (helo=localhost) by stedding.saclay.inria.fr with local-esmtp (Exim 4.80) (envelope-from ) id 1UI06h-00022M-9f for gcc-patches@gcc.gnu.org; Tue, 19 Mar 2013 18:13:51 +0100 Date: Tue, 19 Mar 2013 18:13:51 +0100 (CET) From: Marc Glisse To: gcc-patches@gcc.gnu.org Subject: [RTL] Canonicalize commutative operations more Message-ID: User-Agent: Alpine 2.02 (DEB 1266 2009-07-14) MIME-Version: 1.0 Hello, as explained in the PR, the goal of this patch is to have a more canonical form for RTL expressions, so it is easier to model them with a small number of patterns. This patch passes bootstrap+testsuite on x86_64-linux-gnu. Using the opposite arbitrary order in compare_commutative_operands_precedence (exchange x and y in the line with GET_CODE) passes as well. The simplify-rtx bit is because I get an infinite recursion otherwise. Surprisingly, that infinite recursion occurs only in var-tracking, and only for a single file in bootstrap+testsuite (not the same one depending on the arbitrary order). I am not sure that is the best place to break the recursion, but it seems to work. I don't really expect the patch to be accepted as is, but it seems good enough to start the conversation. 2013-03-19 Marc Glisse PR rtl-optimization/55611 * rtl.h (commutative_operand_precedence): Remove. (compare_commutative_operands_precedence): Declare. * optabs.c (swap_commutative_operands_with_target): Use compare_commutative_operands_precedence. * simplify-rtx.c (simplify_associative_operation): Break the recursion cycle. (simplify_plus_minus_op_data_cmp): Use compare_commutative_operands_precedence. * rtlanal.c (commutative_operand_precedence): Make static. (compare_commutative_operands_precedence): New function. (swap_commutative_operands_p): Use it. Index: rtlanal.c =================================================================== --- rtlanal.c (revision 196633) +++ rtlanal.c (working copy) @@ -3076,21 +3076,21 @@ regno_use_in (unsigned int regno, rtx x) return NULL_RTX; } /* Return a value indicating whether OP, an operand of a commutative operation, is preferred as the first or second operand. The higher the value, the stronger the preference for being the first operand. We use negative values to indicate a preference for the first operand and positive values for the second operand. */ -int +static int commutative_operand_precedence (rtx op) { enum rtx_code code = GET_CODE (op); /* Constants always come the second operand. Prefer "nice" constants. */ if (code == CONST_INT) return -8; if (code == CONST_DOUBLE) return -7; if (code == CONST_FIXED) @@ -3138,28 +3138,43 @@ commutative_operand_precedence (rtx op) case RTX_UNARY: /* Then prefer NEG and NOT. */ if (code == NEG || code == NOT) return 1; default: return 0; } } +/* Return < 0 if it is necessary to swap operands of commutative operation + in order to canonicalize expression, > 0 if it is wrong to swap the + operands, and 0 if we don't know. */ + +int +compare_commutative_operands_precedence (rtx x, rtx y) +{ + int px = commutative_operand_precedence (x); + int py = commutative_operand_precedence (y); + if (px != py) + return px - py; + + /* Use some arbitrary order to avoid pattern explosion. */ + return (int) GET_CODE (x) - (int) GET_CODE (y); +} + /* Return 1 iff it is necessary to swap operands of commutative operation in order to canonicalize expression. */ bool swap_commutative_operands_p (rtx x, rtx y) { - return (commutative_operand_precedence (x) - < commutative_operand_precedence (y)); + return compare_commutative_operands_precedence (x, y) < 0; } /* Return 1 if X is an autoincrement side effect and the register is not the stack pointer. */ int auto_inc_p (const_rtx x) { switch (GET_CODE (x)) { case PRE_INC: Index: optabs.c =================================================================== --- optabs.c (revision 196633) +++ optabs.c (working copy) @@ -1285,33 +1285,29 @@ expand_simple_binop (enum machine_mode m rtx op1, rtx target, int unsignedp, enum optab_methods methods) { optab binop = code_to_optab (code); gcc_assert (binop); return expand_binop (mode, binop, op0, op1, target, unsignedp, methods); } /* Return whether OP0 and OP1 should be swapped when expanding a commutative - binop. Order them according to commutative_operand_precedence and, if - possible, try to put TARGET or a pseudo first. */ + binop. Order them according to compare_commutative_operands_precedence and, + if possible, try to put TARGET or a pseudo first. */ static bool swap_commutative_operands_with_target (rtx target, rtx op0, rtx op1) { - int op0_prec = commutative_operand_precedence (op0); - int op1_prec = commutative_operand_precedence (op1); + int cmp = compare_commutative_operands_precedence (op0, op1); - if (op0_prec < op1_prec) - return true; - - if (op0_prec > op1_prec) - return false; + if (cmp != 0) + return cmp < 0; /* With equal precedence, both orders are ok, but it is better if the first operand is TARGET, or if both TARGET and OP0 are pseudos. */ if (target == 0 || REG_P (target)) return (REG_P (op1) && !REG_P (op0)) || target == op1; else return rtx_equal_p (op1, target); } /* Return true if BINOPTAB implements a shift operation. */ Index: simplify-rtx.c =================================================================== --- simplify-rtx.c (revision 196633) +++ simplify-rtx.c (working copy) @@ -2076,22 +2076,24 @@ simplify_associative_operation (enum rtx if (! swap_commutative_operands_p (op1, op0)) return simplify_gen_binary (code, mode, op1, op0); tem = op0; op0 = op1; op1 = tem; } if (GET_CODE (op0) == code) { - /* Canonicalize "(x op c) op y" as "(x op y) op c". */ - if (swap_commutative_operands_p (XEXP (op0, 1), op1)) + /* Canonicalize "(x op c) op y" as "(x op y) op c". + GET_CODE != code is here to avoid an infinite recursion. */ + if (GET_CODE (XEXP (op0, 1)) != code + && swap_commutative_operands_p (XEXP (op0, 1), op1)) { tem = simplify_gen_binary (code, mode, XEXP (op0, 0), op1); return simplify_gen_binary (code, mode, tem, XEXP (op0, 1)); } /* Attempt to simplify "(a op b) op c" as "a op (b op c)". */ tem = simplify_binary_operation (code, mode, XEXP (op0, 1), op1); if (tem != 0) return simplify_gen_binary (code, mode, XEXP (op0, 0), tem); @@ -4158,26 +4160,24 @@ simplify_const_binary_operation (enum rt struct simplify_plus_minus_op_data { rtx op; short neg; }; static bool simplify_plus_minus_op_data_cmp (rtx x, rtx y) { - int result; + int result = compare_commutative_operands_precedence (x, y); - result = (commutative_operand_precedence (y) - - commutative_operand_precedence (x)); if (result) - return result > 0; + return result < 0; /* Group together equal REGs to do more simplification. */ if (REG_P (x) && REG_P (y)) return REGNO (x) > REGNO (y); else return false; } static rtx simplify_plus_minus (enum rtx_code code, enum machine_mode mode, rtx op0, Index: rtl.h =================================================================== --- rtl.h (revision 196633) +++ rtl.h (working copy) @@ -2015,21 +2015,21 @@ extern rtx get_call_rtx_from (rtx); extern HOST_WIDE_INT get_integer_term (const_rtx); extern rtx get_related_value (const_rtx); extern bool offset_within_block_p (const_rtx, HOST_WIDE_INT); extern void split_const (rtx, rtx *, rtx *); extern bool unsigned_reg_p (rtx); extern int reg_mentioned_p (const_rtx, const_rtx); extern int count_occurrences (const_rtx, const_rtx, int); extern int reg_referenced_p (const_rtx, const_rtx); extern int reg_used_between_p (const_rtx, const_rtx, const_rtx); extern int reg_set_between_p (const_rtx, const_rtx, const_rtx); -extern int commutative_operand_precedence (rtx); +extern int compare_commutative_operands_precedence (rtx, rtx); extern bool swap_commutative_operands_p (rtx, rtx); extern int modified_between_p (const_rtx, const_rtx, const_rtx); extern int no_labels_between_p (const_rtx, const_rtx); extern int modified_in_p (const_rtx, const_rtx); extern int reg_set_p (const_rtx, const_rtx); extern rtx single_set_2 (const_rtx, const_rtx); extern int multiple_sets (const_rtx); extern int set_noop_p (const_rtx); extern int noop_move_p (const_rtx); extern rtx find_last_value (rtx, rtx *, rtx, int);