From patchwork Tue Oct 3 11:55:35 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 820866 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-463389-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="x96hoXgU"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3y5yCt2pdnz9t2c for ; Tue, 3 Oct 2017 22:55:52 +1100 (AEDT) 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:cc:subject:message-id:reply-to:references:mime-version :content-type:in-reply-to; q=dns; s=default; b=GDBnj4ivoDNVsUVus 5e8OvTcN+4JgDcflP4LBpV5oOUUi9H4zbVJi27Zc5pz63+Yjpom/ZihBaEb88WAM JeDUWHqSDJxrMm20iWkUFiQdItnXZ7L5/5y+Ia4SDSPnptOf4IaLn1dHU3N0xRhv aK0ZGCpn/1HD+dy0oH2wV2bKkE= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:reply-to:references:mime-version :content-type:in-reply-to; s=default; bh=re5KRZ9bZHcvw3S+21k1eAR BtfI=; b=x96hoXgUGTAuaYBjBRYP9bW3z5bDgmdIexPC1S4xcRAphDSTUYm+Uyv Ivf0rOp58TSEzbN6hsjxaWDdyJz9m6BR1LuKKdoFvd/yq4Txf9xlpDT68odu5eiQ g5OdmMwy3il4etqnCgTX8bq3p0WSU8KQ2Mw4t5EsXfAMIsBVQSMM= Received: (qmail 28057 invoked by alias); 3 Oct 2017 11:55:45 -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 28044 invoked by uid 89); 3 Oct 2017 11:55:43 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.9 required=5.0 tests=BAYES_00, GIT_PATCH_2, GIT_PATCH_3, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 03 Oct 2017 11:55:42 +0000 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 4DBDBC04AC6B; Tue, 3 Oct 2017 11:55:40 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 4DBDBC04AC6B Authentication-Results: ext-mx07.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx07.extmail.prod.ext.phx2.redhat.com; spf=fail smtp.mailfrom=jakub@redhat.com Received: from tucnak.zalov.cz (ovpn-116-41.ams2.redhat.com [10.36.116.41]) by smtp.corp.redhat.com (Postfix) with ESMTPS id E75835C542; Tue, 3 Oct 2017 11:55:39 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.15.2/8.15.2) with ESMTP id v93BtapB023517; Tue, 3 Oct 2017 13:55:37 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.15.2/8.15.2/Submit) id v93BtZKq023516; Tue, 3 Oct 2017 13:55:35 +0200 Date: Tue, 3 Oct 2017 13:55:35 +0200 From: Jakub Jelinek To: Richard Biener , Alexander Monakov Cc: Kugan Vivekanandarajah , gcc-patches@gcc.gnu.org Subject: [PATCH] Fix sort_by_operand_rank with qsort checking (PR tree-optimization/82381, #2) Message-ID: <20171003115535.GK18588@tucnak> Reply-To: Jakub Jelinek References: <20171003100021.GJ18588@tucnak> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.7.1 (2016-10-04) X-IsSubscribed: yes On Tue, Oct 03, 2017 at 01:24:32PM +0300, Alexander Monakov wrote: > On Tue, 3 Oct 2017, Jakub Jelinek wrote: > > The qsort cmp transitivity checks may fail with the sort_by_operand_rank > > comparator, because if one of the operands has stmt_to_insert and the > > other doesn't (but likely also if one SSA_NAME is (D) and the other is not), > > we fallthrough into SSA_NAME_VERSION comparison, but if both aren't (D) and > > both don't have stmt_to_insert, we use different comparison rules. > > When looking at the code I've noticed another issue, so the fix seems > incomplete (but I don't know if the other problem can/should be fixed > independently), see below: > > > > --- gcc/tree-ssa-reassoc.c.jj 2017-10-02 17:33:14.270282226 +0200 > > +++ gcc/tree-ssa-reassoc.c 2017-10-02 18:18:07.328611132 +0200 > > @@ -514,36 +514,37 @@ sort_by_operand_rank (const void *pa, co > > && TREE_CODE (oea->op) == SSA_NAME > > && TREE_CODE (oeb->op) == SSA_NAME) > > { > > The containing if statement condition reads: > > if (oeb->rank == oea->rank > && TREE_CODE (oea->op) == SSA_NAME > && TREE_CODE (oeb->op) == SSA_NAME) > > so as far as I can tell it's possible to have items A, B, C such that > all have same rank, A and C correspond to SSA_NAMEs and compare C < A, > but B does not, so comparisons of A or C against B fall down to > > return oeb->id > oea->id ? 1 : -1; > > and ultimately result in A < B < C < A. I think it is likely only hypothetical, because get_rank for non-SSA_NAME should be 0 and thus handled earlier (for SSA_NAME I think rank of 0 is still possible). That said, this untested patch reshuffles stuff a little bit, ok for trunk if it passes testing? 2017-10-03 Jakub Jelinek PR tree-optimization/82381 * tree-ssa-reassoc.c (sort_by_operand_rank): Check for different oeN->rank first. Return 1 or -1 if one op is SSA_NAME and the other is not. Jakub --- gcc/tree-ssa-reassoc.c.jj 2017-10-03 13:24:00.000000000 +0200 +++ gcc/tree-ssa-reassoc.c 2017-10-03 13:41:23.098183270 +0200 @@ -495,10 +495,13 @@ sort_by_operand_rank (const void *pa, co const operand_entry *oea = *(const operand_entry *const *)pa; const operand_entry *oeb = *(const operand_entry *const *)pb; + if (oeb->rank != oea->rank) + return oeb->rank > oea->rank ? 1 : -1; + /* It's nicer for optimize_expression if constants that are likely - to fold when added/multiplied//whatever are put next to each + to fold when added/multiplied/whatever are put next to each other. Since all constants have rank 0, order them by type. */ - if (oeb->rank == 0 && oea->rank == 0) + if (oea->rank == 0) { if (constant_type (oeb->op) != constant_type (oea->op)) return constant_type (oeb->op) - constant_type (oea->op); @@ -508,51 +511,50 @@ sort_by_operand_rank (const void *pa, co return oeb->id > oea->id ? 1 : -1; } + if (TREE_CODE (oea->op) != SSA_NAME) + { + if (TREE_CODE (oeb->op) != SSA_NAME) + return oeb->id > oea->id ? 1 : -1; + else + return 1; + } + else if (TREE_CODE (oeb->op) != SSA_NAME) + return -1; + /* Lastly, make sure the versions that are the same go next to each other. */ - if (oeb->rank == oea->rank - && TREE_CODE (oea->op) == SSA_NAME - && TREE_CODE (oeb->op) == SSA_NAME) + if (SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op)) { - if (SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op)) + /* As SSA_NAME_VERSION is assigned pretty randomly, because we reuse + versions of removed SSA_NAMEs, so if possible, prefer to sort + based on basic block and gimple_uid of the SSA_NAME_DEF_STMT. + See PR60418. */ + gimple *stmta = SSA_NAME_DEF_STMT (oea->op); + gimple *stmtb = SSA_NAME_DEF_STMT (oeb->op); + basic_block bba = gimple_bb (stmta); + basic_block bbb = gimple_bb (stmtb); + if (bbb != bba) { - /* As SSA_NAME_VERSION is assigned pretty randomly, because we reuse - versions of removed SSA_NAMEs, so if possible, prefer to sort - based on basic block and gimple_uid of the SSA_NAME_DEF_STMT. - See PR60418. */ - gimple *stmta = SSA_NAME_DEF_STMT (oea->op); - gimple *stmtb = SSA_NAME_DEF_STMT (oeb->op); - basic_block bba = gimple_bb (stmta); - basic_block bbb = gimple_bb (stmtb); - if (bbb != bba) - { - /* One of the SSA_NAMEs can be defined in oeN->stmt_to_insert - but the other might not. */ - if (!bba) - return 1; - if (!bbb) - return -1; - /* If neither is, compare bb_rank. */ - if (bb_rank[bbb->index] != bb_rank[bba->index]) - return bb_rank[bbb->index] - bb_rank[bba->index]; - } - - bool da = reassoc_stmt_dominates_stmt_p (stmta, stmtb); - bool db = reassoc_stmt_dominates_stmt_p (stmtb, stmta); - if (da != db) - return da ? 1 : -1; - - return (SSA_NAME_VERSION (oeb->op) > SSA_NAME_VERSION (oea->op) - ? 1 : -1); + /* One of the SSA_NAMEs can be defined in oeN->stmt_to_insert + but the other might not. */ + if (!bba) + return 1; + if (!bbb) + return -1; + /* If neither is, compare bb_rank. */ + if (bb_rank[bbb->index] != bb_rank[bba->index]) + return bb_rank[bbb->index] - bb_rank[bba->index]; } - else - return oeb->id > oea->id ? 1 : -1; + + bool da = reassoc_stmt_dominates_stmt_p (stmta, stmtb); + bool db = reassoc_stmt_dominates_stmt_p (stmtb, stmta); + if (da != db) + return da ? 1 : -1; + + return SSA_NAME_VERSION (oeb->op) > SSA_NAME_VERSION (oea->op) ? 1 : -1; } - if (oeb->rank != oea->rank) - return oeb->rank > oea->rank ? 1 : -1; - else - return oeb->id > oea->id ? 1 : -1; + return oeb->id > oea->id ? 1 : -1; } /* Add an operand entry to *OPS for the tree operand OP. */