From patchwork Thu Jan 23 22:13:20 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 1228583 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-518185-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha1 header.s=default header.b=g67qKvrl; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=FRV4MGzf; 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 483c431gmGz9s1x for ; Fri, 24 Jan 2020 09:13:39 +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:from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type:content-transfer-encoding; q=dns; s= default; b=fXv4uCpV1vbUMRLzL07qNY7LlMJ40xWu3TYkwxKserCvoirC6euTh FMTqmAK6+uPZey6RggwWO5wlV02RLy6QT8szGZxFBK9I0G009m5fKdM6SjYn0qsm UJllJOU1ennKUSJX7dK5zYxAaYm6GyTW0D4OTsNjpxbcvKoZ2Tlii4= 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:from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type:content-transfer-encoding; s=default; bh=2tMk21M3roxeAo7Lr/GTZDlayno=; b=g67qKvrlN4krEPuepwqRzx7GpzjJ Na/5iWmQEnewbH+IGE9aIS4unZTMpdNpUztVkauIOa97cmZboDRkDMBidIutUtL6 wPmHp00jv+zBF2vYyCa1LhpdUCkRT/YWL3IDRXyzG+uDM8fwkoG/U+/kHaVQZaVA Gpmds4qUYdvKqCs= Received: (qmail 791 invoked by alias); 23 Jan 2020 22:13:31 -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 783 invoked by uid 89); 23 Jan 2020 22:13:31 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-23.3 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 spammy= X-HELO: us-smtp-delivery-1.mimecast.com Received: from us-smtp-2.mimecast.com (HELO us-smtp-delivery-1.mimecast.com) (207.211.31.81) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 23 Jan 2020 22:13:29 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1579817608; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=yiKYEb3pZtK99CmJ74qB06KO1eZ299UVJcxPl3v0OMc=; b=FRV4MGzfpY+TpiGnWR8uXSjHR7H2FFKZ31QoAplDIvEVckowuXpek+ZE/F9JFHr9Xxz75J YJDpW3u2IonaOuCib5DaccBBxD9Nocm6DfKC2qqQTDXNzOKo/8Lz/vWWOQ43hAPDD7u6/S aFF2DoqWcrnZMo93dxGaq1GCBLj52xA= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-263-mxhHb3nfMISIkXSdgGQ5dg-1; Thu, 23 Jan 2020 17:13:24 -0500 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 233D9800D5A; Thu, 23 Jan 2020 22:13:23 +0000 (UTC) Received: from t470.redhat.com (ovpn-117-41.phx2.redhat.com [10.3.117.41]) by smtp.corp.redhat.com (Postfix) with ESMTP id 4D0C15DA2C; Thu, 23 Jan 2020 22:13:21 +0000 (UTC) From: David Malcolm To: Alexander Monakov , Jakub Jelinek Cc: Stefan Schulze Frielinghaus , gcc-patches@gcc.gnu.org, David Malcolm Subject: [PATCH] analyzer: fixes to tree_cmp and other comparators Date: Thu, 23 Jan 2020 17:13:20 -0500 Message-Id: <20200123221320.21440-1-dmalcolm@redhat.com> In-Reply-To: References: MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-IsSubscribed: yes On Thu, 2020-01-23 at 18:46 +0300, Alexander Monakov wrote: > On Thu, 23 Jan 2020, David Malcolm wrote: > > > Removing the assertions fixes it for me (a stage1 build, at least, > > and > > it then passes the testsuite). > > > > I've made this blunder in four places in the analyzer: > > > > call-string.cc:162: call_string::cmp > > program-point.cc:461: function_point::cmp_within_supernode > > These two don't raise concerns on brief inspection. > > > engine.cc:1820: worklist::key_t::cmp > > This one tries to use signed difference of hashes as return value, > this is > not going to work in general while passing your assert almost always > (except > when difference of hashes is exactly -2^31). The problem is, > difference of > hashes leads to non-transitive comparison and qsort_chk can catch it > on a > suitable testcase. > > > region-model.cc:1878: tree_cmp > > This is the one under discussion here. > > > IIRC, I added these checks as I was finding it difficult to debug > > things when qsort_chk failed - the first three of the comparators > > in > > the list above build on each other: worklist::key_t::cmp uses both > > function_point::cmp_within_supernode and call_string::cmp (and > > various > > other things), so if the worklist qsort_chk fails, it sometimes > > required a fair bit of digging into which of the nested comparators > > had > > failed (also, all the void * don't help; I'd love to have a > > template > > that does a typesafe qsort without needing casts in the > > comparator). > > FWIW qsort_chk_error is a separate function to make that easier: if > you place a > breakpoint on qsort_chk_error you just need to step a few times to > get into a > comparator that is under suspicion, and don't need to type out casts > in gdb. > > Alexander Thanks - that makes much more sense to me now. How does the following patch look: region_model.cc's tree_cmp attempted to verify that the ordering is symmetric by asserting that tree_cmp (x, y) == -tree_cmp (y, x) This condition is too strong: it's only required for a comparator that sign (tree_cmp (x, y)) == -sign (tree_cmp (y, x)) and the incorrect form of the assertion doesn't hold e.g. on s390x where for certain inputs x, y, tree_cmp (x, y) == 1 and tree_cmp (y, x) == -2, breaking the build in "make selftest" in stage1. In any case, these checks are redundant, since qsort_chk performs them. Additionally, there is a potential lack of transitivity in worklist::key_t::cmp where hashval_t values are compared by subtraction, which could fail to be transitive if overflows occur. This patch eliminates the redundant checks and reimplements the hashval_t comparisons in terms of < and >, fixing these issues. Fixes build on s390x-ibm-linux-gnu for stage 1, at least, with no testsuite regressions. Full bootstrap and regression test run in progress. OK for master if it passes? gcc/analyzer/ChangeLog: * call-string.cc (call_string::cmp_1): Delete, moving body to... (call_string::cmp): ...here. * call-string.h (call_string::cmp_1): Delete decl. * engine.cc (worklist::key_t::cmp_1): Delete, moving body to... (worklist::key_t::cmp): ...here. Implement hash comparisons via comparison rather than subtraction to avoid overflow issues. * exploded-graph.h (worklist::key_t::cmp_1): Delete decl. * region-model.cc (tree_cmp): Eliminate buggy checking for symmetry. --- gcc/analyzer/call-string.cc | 23 +---------------------- gcc/analyzer/call-string.h | 3 --- gcc/analyzer/engine.cc | 35 +++++++---------------------------- gcc/analyzer/exploded-graph.h | 1 - gcc/analyzer/region-model.cc | 16 +--------------- 5 files changed, 9 insertions(+), 69 deletions(-) diff --git a/gcc/analyzer/call-string.cc b/gcc/analyzer/call-string.cc index 3d398c39a88..288953ed37c 100644 --- a/gcc/analyzer/call-string.cc +++ b/gcc/analyzer/call-string.cc @@ -149,6 +149,7 @@ call_string::calc_recursion_depth () const } /* Comparator for call strings. + This implements a version of lexicographical order. Return negative if A is before B. Return positive if B is after A. Return 0 if they are equal. */ @@ -156,28 +157,6 @@ call_string::calc_recursion_depth () const int call_string::cmp (const call_string &a, const call_string &b) -{ - int result = cmp_1 (a, b); - - /* Check that the ordering is symmetric */ -#if CHECKING_P - int reversed = cmp_1 (b, a); - gcc_assert (reversed == -result); -#endif - - /* We should only have 0 for equal pairs. */ - gcc_assert (result != 0 - || a == b); - - return result; -} - -/* Implementation of call_string::cmp. - This implements a version of lexicographical order. */ - -int -call_string::cmp_1 (const call_string &a, - const call_string &b) { unsigned len_a = a.length (); unsigned len_b = b.length (); diff --git a/gcc/analyzer/call-string.h b/gcc/analyzer/call-string.h index 5e362d8cadb..1b5db0a4a20 100644 --- a/gcc/analyzer/call-string.h +++ b/gcc/analyzer/call-string.h @@ -69,9 +69,6 @@ public: void validate () const; private: - static int cmp_1 (const call_string &a, - const call_string &b); - auto_vec m_return_edges; }; diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index 1fdedf49224..939401140e7 100644 --- a/gcc/analyzer/engine.cc +++ b/gcc/analyzer/engine.cc @@ -1634,7 +1634,7 @@ worklist::add_node (exploded_node *enode) Return 0 if they are equal. */ int -worklist::key_t::cmp_1 (const worklist::key_t &ka, const worklist::key_t &kb) +worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb) { const program_point &point_a = ka.m_enode->get_point (); const program_point &point_b = kb.m_enode->get_point (); @@ -1710,9 +1710,12 @@ worklist::key_t::cmp_1 (const worklist::key_t &ka, const worklist::key_t &kb) sm_state_map *smap_a = state_a.m_checker_states[sm_idx]; sm_state_map *smap_b = state_b.m_checker_states[sm_idx]; - int sm_cmp = smap_a->hash () - smap_b->hash (); - if (sm_cmp) - return sm_cmp; + hashval_t hash_a = smap_a->hash (); + hashval_t hash_b = smap_b->hash (); + if (hash_a < hash_b) + return -1; + else if (hash_a > hash_b) + return 1; } /* Otherwise, we have two enodes at the same program point but with @@ -1722,30 +1725,6 @@ worklist::key_t::cmp_1 (const worklist::key_t &ka, const worklist::key_t &kb) return ka.m_enode->m_index - kb.m_enode->m_index; } -/* Comparator for implementing worklist::key_t comparison operators. - Return negative if KA is before KB - Return positive if KA is after KB - Return 0 if they are equal. */ - -int -worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb) -{ - int result = cmp_1 (ka, kb); - - /* Check that the ordering is symmetric */ -#if CHECKING_P - int reversed = cmp_1 (kb, ka); - gcc_assert (reversed == -result); -#endif - - /* We should only have 0 for equal (point, state) pairs. */ - gcc_assert (result != 0 - || (*ka.m_enode->get_ps_key () - == *kb.m_enode->get_ps_key ())); - - return result; -} - /* exploded_graph's ctor. */ exploded_graph::exploded_graph (const supergraph &sg, logger *logger, diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h index a3e758ed751..c72319cb5c1 100644 --- a/gcc/analyzer/exploded-graph.h +++ b/gcc/analyzer/exploded-graph.h @@ -652,7 +652,6 @@ private: } private: - static int cmp_1 (const key_t &ka, const key_t &kb); static int cmp (const key_t &ka, const key_t &kb); int get_scc_id (const exploded_node *enode) const diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index 985f1bd56ac..a986549b597 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -1843,21 +1843,7 @@ tree_cmp (const void *p1, const void *p2) const_tree t1 = *(const_tree const *)p1; const_tree t2 = *(const_tree const *)p2; - int result = tree_cmp (t1, t2); - - /* Check that the ordering is symmetric */ -#if CHECKING_P - int reversed = tree_cmp (t2, t1); - gcc_assert (reversed == -result); -#endif - - /* We should only have 0 for equal pairs. */ -#if 0 - gcc_assert (result != 0 - || t1 == t2); -#endif - - return result; + return tree_cmp (t1, t2); } /* Attempt to merge MAP_REGION_A and MAP_REGION_B into MERGED_MAP_REGION,