From patchwork Tue Jul 5 17:43:39 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1652646 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=Kmz9nA2b; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4LcqmY0V0fz9s1l for ; Wed, 6 Jul 2022 03:44:11 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A8476385742E for ; Tue, 5 Jul 2022 17:44:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A8476385742E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1657043046; bh=4HuVFWWG36v8LS1ym83hC9C5aYD0T7j20OSSXy1+suE=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=Kmz9nA2byXTvohkr/irSqldDRDFZSokcbjAIdW2xtxJROmr0wmF2xyJC0M7gqRebH H1q277VkeIrfovScqQkqGAkabigbmW/UvVJqGvzVeX5XGM1WBlcBlZ0/A0Sfpsj7C/ 2jzyYGRHGPVgEtvIOYYPQ6osfhw94xx7Lphurqsk= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 070153858292 for ; Tue, 5 Jul 2022 17:43:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 070153858292 Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-207-3kbCG9KvMRev9VcIBb4FrQ-1; Tue, 05 Jul 2022 13:43:43 -0400 X-MC-Unique: 3kbCG9KvMRev9VcIBb4FrQ-1 Received: by mail-qk1-f197.google.com with SMTP id bm2-20020a05620a198200b006a5dac37fa2so12122262qkb.16 for ; Tue, 05 Jul 2022 10:43:43 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent :content-language:to:cc:from:subject; bh=QEWCZMsy+8VaQ8DNhqq9Y5jNZNwlUZtEozuD4nhli7A=; b=WflLfPGjUx6linPZ3CjgfdKMMSsffHPLmg0qj2TKnFqljIAnNmbjDlLW5kIXlHsfp7 jPVYvw5lSkOpLFuXLLy9CCow1lZkUuU0UpJ9JILpaZzS4yqmuYIpkDWPfuiBeW739RFz TbLL07Pw4CJgd7SviloqdIgD33dgr5kt2Kfq7XXnsR8LvdjDQXNVewy4t/02qW8Hrov7 3TiIqb9AWnThAhGe9COxlemN+NgfgkJrMsZDJYtDC0NCLpWVAqVreZEP2v9/WHVY0XDS IED3BcfUYyzuy4XtbjPOUFS+MCDgRxjigboDF/St1ZnaO5TSuf6kTLERGSFCOY93i31e i4yA== X-Gm-Message-State: AJIora9HYmIQOAUQ3oI1RKJZ/2kYiAper7FRiLO3FJTbUbgILwrKhhbp aOolnbGTm7EFokoePwGLe7aodINsHqJCM206l43KxQQIBLCMa0V8/oCGDuUpeVkhj+Ms93/kxC0 lvceFAb6sPEf7B6QlCFy0591RYfTf1KX93pj439L567Hq9aN+VmXvqILtO2bCLSucx6nvHA== X-Received: by 2002:a05:622a:183:b0:31d:2639:af02 with SMTP id s3-20020a05622a018300b0031d2639af02mr29007874qtw.377.1657043022490; Tue, 05 Jul 2022 10:43:42 -0700 (PDT) X-Google-Smtp-Source: AGRyM1u9xY9BnfqZpclRd/tnC5BH8b0EJ9tEtm57lEFDbzYbnPtRoHQ6AQQ9H3PQ+k8gxMwVqFGp5g== X-Received: by 2002:a05:622a:183:b0:31d:2639:af02 with SMTP id s3-20020a05622a018300b0031d2639af02mr29007858qtw.377.1657043022140; Tue, 05 Jul 2022 10:43:42 -0700 (PDT) Received: from [192.168.0.102] ([104.219.127.152]) by smtp.gmail.com with ESMTPSA id g19-20020ac87d13000000b00307aed25fc7sm23918995qtb.31.2022.07.05.10.43.40 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 05 Jul 2022 10:43:41 -0700 (PDT) Message-ID: <1bc05212-1258-2c0f-bf57-65e11bbeb919@redhat.com> Date: Tue, 5 Jul 2022 13:43:39 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 To: gcc-patches Subject: [COMMITTED] Provide a relation verification mechanism. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" the relation oracle works on a purely symbolic basis. It assumes for instance that x == x, along with everything in the equivalency set. With the coming introduction of floating point ranges, we have circumstances beyond the symbol relation which can affect the result.  If the range of X may contain a NaN, then  x != x. Within ranger, folding these sorts of things is not much of an issue.  For x == x when we invoke fold_range (==, range x, range x, VREL_EQ) that will be dispatched to the floating point version of operator_equal() which first checks if either operand has a Nan, and if so, ignores the incoming equality relation. Although there are no current clients of the relation oracle outside of ranger, I see the potential need for a mechanism to validate any relation returned by the oracle with specific ranges or ssa-names.  I don't *THINK* we need this within ranger yet, but haven't been able to convince myself 100% yet :-). This patch adds 2 new API entry points to the oracle:   relation_kind validate_relation (relation_kind k, tree ssa1, tree ssa2);   relation_kind validate_relation (relation_kind k, vrange &op1, vrange &op2); They basically do what ranger currently does, takes the relation and checks to see if folding the appropriate expression with the relation returns the expected [1, 1] ie  it tries folding     fold_range (r, EQ_EXPR, op1, op2, VREL_EQ)  and returns either VREL_EQ if the result is [1, 1], or VREL_VARYING otherwise.  so if op1 or op2 had a NaN, then we'd get VREL_VARYING .   The ssa-name version simply uses a value of VARYING of the approrate type. Anyway, Ive tested it on all the integer code by having the oracle always validate any relation it returns. which bootstraps with no regressions on 86_64-pc-linux-gnu. The default I have checked in does not actually call these new routines.  but they are there when we need them now. Andrew PS. It also allows x == x to be registered to the oracle, which use to trap for no really good reason. From 1d2aa262482fc9b23201200ca82aa3b8659b072e Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 5 Jul 2022 10:54:26 -0400 Subject: [PATCH] Provide a relation verification mechanism. Provide a relation oracle API which validates a relation between 2 ranges. This allows relation queries that are symbolicly true to be overridden by range specific information. ie. x == x is true symbolically, but for floating point a NaN may invalidate this assumption. * value-relation.cc (relation_to_code): New vector. (relation_oracle::validate_relation): New. (set_relation): Allow ssa1 == ssa2 to be registered. * value-relation.h (validate_relation): New prototype. (query_relation): Make internal variant protected. --- gcc/value-relation.cc | 70 +++++++++++++++++++++++++++++++++++++++++-- gcc/value-relation.h | 10 +++++-- 2 files changed, 75 insertions(+), 5 deletions(-) diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index 85d159f5d96..13ce44199f7 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -184,6 +184,71 @@ relation_transitive (relation_kind r1, relation_kind r2) return rr_transitive_table[r1][r2]; } +// This vector maps a relation to the equivalent tree code. + +tree_code relation_to_code [VREL_LAST + 1] = { + ERROR_MARK, ERROR_MARK, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EQ_EXPR, + NE_EXPR }; + +// This routine validates that a relation can be applied to a specific set of +// ranges. In particular, floating point x == x may not be true if the NaN bit +// is set in the range. Symbolically the oracle will determine x == x, +// but specific range instances may override this. +// To verify, attempt to fold the relation using the supplied ranges. +// One would expect [1,1] to be returned, anything else means there is something +// in the range preventing the relation from applying. +// If there is no mechanism to verify, assume the relation is acceptable. + +relation_kind +relation_oracle::validate_relation (relation_kind rel, vrange &op1, vrange &op2) +{ + // If there is no mapping to a tree code, leave the relation as is. + tree_code code = relation_to_code [rel]; + if (code == ERROR_MARK) + return rel; + + // Undefined ranges cannot be checked either. + if (op1.undefined_p () || op2.undefined_p ()) + return rel; + + tree t1 = op1.type (); + tree t2 = op2.type (); + + // If the range types are not compatible, no relation can exist. + if (!range_compatible_p (t1, t2)) + return VREL_VARYING; + + // If there is no handler, leave the relation as is. + range_op_handler handler (code, t1); + if (!handler) + return rel; + + // If the relation cannot be folded for any reason, leave as is. + Value_Range result (boolean_type_node); + if (!handler.fold_range (result, boolean_type_node, op1, op2, rel)) + return rel; + + // The expression op1 REL op2 using REL should fold to [1,1]. + // Any other result means the relation is not verified to be true. + if (result.varying_p () || result.zero_p ()) + return VREL_VARYING; + + return rel; +} + +// If no range is available, create a varying range for each SSA name and +// verify. + +relation_kind +relation_oracle::validate_relation (relation_kind rel, tree ssa1, tree ssa2) +{ + Value_Range op1, op2; + op1.set_varying (TREE_TYPE (ssa1)); + op2.set_varying (TREE_TYPE (ssa2)); + + return validate_relation (rel, op1, op2); +} + // Given an equivalence set EQUIV, set all the bits in B that are still valid // members of EQUIV in basic block BB. @@ -602,7 +667,8 @@ private: inline void value_relation::set_relation (relation_kind r, tree n1, tree n2) { - gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2)); + gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2) + || r == VREL_EQ); related = r; name1 = n1; name2 = n2; @@ -1199,7 +1265,7 @@ dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) if (kind != VREL_VARYING) return kind; - // Query using the equiovalence sets. + // Query using the equivalence sets. kind = query_relation (bb, equiv1, equiv2); return kind; } diff --git a/gcc/value-relation.h b/gcc/value-relation.h index 478729be0bf..77e12085eea 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -95,15 +95,19 @@ public: virtual void register_relation (basic_block, relation_kind, tree, tree) = 0; // Query for a relation between two ssa names in a basic block. virtual relation_kind query_relation (basic_block, tree, tree) = 0; - // Query for a relation between two equivalency stes in a basic block. - virtual relation_kind query_relation (basic_block, const_bitmap, - const_bitmap) = 0; + + relation_kind validate_relation (relation_kind, tree, tree); + relation_kind validate_relation (relation_kind, vrange &, vrange &); virtual void dump (FILE *, basic_block) const = 0; virtual void dump (FILE *) const = 0; void debug () const; protected: void valid_equivs (bitmap b, const_bitmap equivs, basic_block bb); + // Query for a relation between two equivalency sets in a basic block. + virtual relation_kind query_relation (basic_block, const_bitmap, + const_bitmap) = 0; + friend class path_oracle; }; // This class represents an equivalency set, and contains a link to the next -- 2.17.2