From patchwork Thu Oct 5 19:04:37 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1844130 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=Tru90r0Q; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4S1gwx5n6Sz1yq9 for ; Fri, 6 Oct 2023 06:05:05 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9D8A7385C6F6 for ; Thu, 5 Oct 2023 19:05:03 +0000 (GMT) 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.133.124]) by sourceware.org (Postfix) with ESMTPS id 3E6B33858C39 for ; Thu, 5 Oct 2023 19:04:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 3E6B33858C39 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1696532689; 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; bh=K47R1h8qB8n77MjLWRIvBqtzub3IW1p2ey05F4Llxwo=; b=Tru90r0QJ3nKBwoWdBkzU/a3mUxiiNWmUmk7zXRCVjXlUt2R/FhbSGEJMd4dhM4l0typBV H+94EQeSvFjge5WNFQ6s/8WjmR9gExiABK3eJd+5P0MZVjvG9DgTE16SgkVAMzpJMXu4jL oYzSMfU1UHdovQYuwjaP+n611XCj1MU= Received: from mail-oi1-f198.google.com (mail-oi1-f198.google.com [209.85.167.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-84-RGJG15TYMjK3cfAax44mng-1; Thu, 05 Oct 2023 15:04:37 -0400 X-MC-Unique: RGJG15TYMjK3cfAax44mng-1 Received: by mail-oi1-f198.google.com with SMTP id 5614622812f47-3af5b5d816aso2088272b6e.3 for ; Thu, 05 Oct 2023 12:04:37 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696532676; x=1697137476; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=N/4Nj+lG1DXxbFV2XNAjoYnIzyFDgFsBoNEE67kJ5kw=; b=ENVuMRyGpvYEi6KIXbF9pCKY8zdUbMIw3Peii49XpU0eiYhhzUkqLg/GRShSXlw++X I0y++WeI7JaYqA2xyFBp+vt0KgxXHrJR46i7CAZ0yNKdocEBEfPQtDObQXmkbV2TXb+t TXcEcjFg+cG4y/yj66RpGTkvF4oMsgSxueMrQuLYuHLN73HqUckIOM4j6jcDWIOkNJYM G9AgthXeUFsEj4fGJ1FxguWdIrtrJyKPugPHTWHebLchqIUOCS45EULkh65yLeaPEuTg BXETlW7/N1GCJvUfcyP9JFJlAD9JqK3e+DptEPo8Ijgn33eudQLU52UjtYy2tArAFRUv HZXA== X-Gm-Message-State: AOJu0YzX2x2ZvgneaZ4r6sZb+YLZOD0BZyXoIr+0CsW3UsCX2zsmUAk0 spKEQDM9xAVk9Z6OKziyu5xWzrVILHSgYWNgh2Ap+blLIRzTuy+lGiDRCyEEN3SLKNrUyBOyswk /4oUKHkfxhzAMhnvfFcYJxJLunO6aAaRx3NqQQucYErR7E7DNx0gylp5bfRLMQufx52HHxqGV3o CBSg== X-Received: by 2002:a05:6808:2a7b:b0:3a7:1e86:e83f with SMTP id fu27-20020a0568082a7b00b003a71e86e83fmr6148221oib.51.1696532676170; Thu, 05 Oct 2023 12:04:36 -0700 (PDT) X-Google-Smtp-Source: AGHT+IGlkrgrSkB5X5+qTmKY8N3JNOQk+PIZZHSEHJ6SyKGDhR897SHsV4q0pnpKzDNONCAIu/uxjw== X-Received: by 2002:a05:6808:2a7b:b0:3a7:1e86:e83f with SMTP id fu27-20020a0568082a7b00b003a71e86e83fmr6148203oib.51.1696532675819; Thu, 05 Oct 2023 12:04:35 -0700 (PDT) Received: from [192.168.0.174] ([104.219.124.252]) by smtp.gmail.com with ESMTPSA id a12-20020a0ce38c000000b006365b23b5dfsm712528qvl.23.2023.10.05.12.04.34 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 05 Oct 2023 12:04:35 -0700 (PDT) Message-ID: <490a1ac3-8263-1a11-324c-46f4e92ca970@redhat.com> Date: Thu, 5 Oct 2023 15:04:37 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.13.0 To: gcc-patches Cc: "hernandez, aldy" From: Andrew MacLeod Subject: [COMMITTED 1/3] Add outgoing range vector calculation API. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.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_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP 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.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org This patch adds 2 routine that can be called to generate GORI information. The primar API is: bool gori_on_edge (class ssa_cache &r, edge e, range_query *query = NULL, gimple_outgoing_range *ogr = NULL); This will populate an ssa-cache R with any ranges that are generated by edge E.   It will use QUERY, if provided, to satisfy any incoming values.  if OGR is provided, it is used to pick up hard edge values.. like TRUE, FALSE, or switch edges. It currently only works for TRUE/FALSE conditionals, and doesn't try to solve complex logical combinations.  ie (a <6 && b > 6) || (a>10 || b < 3) as those can get exponential and require multiple evaluations of the IL to satisfy.  It will fully utilize range-ops however and so comes up with many ranges ranger does. It also provides the "raw" ranges on the edge.. ie. it doesn't try to figure out anything outside the current basic block, but rather reflects exactly what the edge indicates. ie:   :   x.0_1 = (unsigned int) x_20(D);   _2 = x.0_1 + 4294967292;   if (_2 > 4)     goto ; [INV]   else     goto ; [INV] produces Edge ranges BB 2->3 x.0_1  : [irange] unsigned int [0, 3][9, +INF] _2  : [irange] unsigned int [5, +INF] x_20(D)  : [irange] int [-INF, 3][9, +INF] Edge ranges BB 2->4 x.0_1  : [irange] unsigned int [4, 8] MASK 0xf VALUE 0x0 _2  : [irange] unsigned int [0, 4] x_20(D)  : [irange] int [4, 8] MASK 0xf VALUE 0x0 It performs a linear walk through juts the required statements, so each of the the above vectors are generated by visiting each of the 3 statements exactly once, so its pretty quick. The other entry point is: bool gori_name_on_edge (vrange &r, tree name, edge e, range_query *q); This does basically the same thing, except it only looks at whether NAME has a range, and returns it if it does.  not other overhead. Pushed. From 52c1e2c805bc2fd7a30583dce3608b738f3a5ce4 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 15 Aug 2023 17:29:58 -0400 Subject: [PATCH 1/3] Add outgoing range vector calcualtion API Provide a GORI API which can produce a range vector for all outgoing ranges on an edge without any of the other infratructure. * gimple-range-gori.cc (gori_stmt_info::gori_stmt_info): New. (gori_calc_operands): New. (gori_on_edge): New. (gori_name_helper): New. (gori_name_on_edge): New. * gimple-range-gori.h (gori_on_edge): New prototype. (gori_name_on_edge): New prototype. --- gcc/gimple-range-gori.cc | 213 +++++++++++++++++++++++++++++++++++++++ gcc/gimple-range-gori.h | 15 +++ 2 files changed, 228 insertions(+) diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index 2694e551d73..1b5eda43390 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -1605,3 +1605,216 @@ gori_export_iterator::get_name () } return NULL_TREE; } + +// This is a helper class to set up STMT with a known LHS for further GORI +// processing. + +class gori_stmt_info : public gimple_range_op_handler +{ +public: + gori_stmt_info (vrange &lhs, gimple *stmt, range_query *q); + Value_Range op1_range; + Value_Range op2_range; + tree ssa1; + tree ssa2; +}; + + +// Uses query Q to get the known ranges on STMT with a LHS range +// for op1_range and op2_range and set ssa1 and ssa2 if either or both of +// those operands are SSA_NAMES. + +gori_stmt_info::gori_stmt_info (vrange &lhs, gimple *stmt, range_query *q) + : gimple_range_op_handler (stmt) +{ + ssa1 = NULL; + ssa2 = NULL; + // Don't handle switches as yet for vector processing. + if (is_a (stmt)) + return; + + // No frther processing for VARYING or undefined. + if (lhs.undefined_p () || lhs.varying_p ()) + return; + + // If there is no range-op handler, we are also done. + if (!*this) + return; + + // Only evaluate logical cases if both operands must be the same as the LHS. + // Otherwise its becomes exponential in time, as well as more complicated. + if (is_gimple_logical_p (stmt)) + { + gcc_checking_assert (range_compatible_p (lhs.type (), boolean_type_node)); + enum tree_code code = gimple_expr_code (stmt); + if (code == TRUTH_OR_EXPR || code == BIT_IOR_EXPR) + { + // [0, 0] = x || y means both x and y must be zero. + if (!lhs.singleton_p () || !lhs.zero_p ()) + return; + } + else if (code == TRUTH_AND_EXPR || code == BIT_AND_EXPR) + { + // [1, 1] = x && y means both x and y must be one. + if (!lhs.singleton_p () || lhs.zero_p ()) + return; + } + } + + tree op1 = operand1 (); + tree op2 = operand2 (); + ssa1 = gimple_range_ssa_p (op1); + ssa2 = gimple_range_ssa_p (op2); + // If both operands are the same, only process one of them. + if (ssa1 && ssa1 == ssa2) + ssa2 = NULL_TREE; + + // Extract current ranges for the operands. + fur_stmt src (stmt, q); + if (op1) + { + op1_range.set_type (TREE_TYPE (op1)); + src.get_operand (op1_range, op1); + } + + // And satisfy the second operand for single op satements. + if (op2) + { + op2_range.set_type (TREE_TYPE (op2)); + src.get_operand (op2_range, op2); + } + else if (op1) + op2_range = op1_range; + return; +} + + +// Process STMT using LHS as the range of the LHS. Invoke GORI processing +// to resolve ranges for all SSA_NAMES feeding STMT which may be altered +// based on LHS. Fill R with the results, and resolve all incoming +// ranges using range-query Q. + +static void +gori_calc_operands (vrange &lhs, gimple *stmt, ssa_cache &r, range_query *q) +{ + struct gori_stmt_info si(lhs, stmt, q); + if (!si) + return; + + Value_Range tmp; + // Now evaluate operand ranges, and set them in the edge cache. + // If there was already a range, leave it and do no further evaluation. + if (si.ssa1 && !r.has_range (si.ssa1)) + { + tmp.set_type (TREE_TYPE (si.ssa1)); + if (si.calc_op1 (tmp, lhs, si.op2_range)) + si.op1_range.intersect (tmp); + r.set_range (si.ssa1, si.op1_range); + gimple *src = SSA_NAME_DEF_STMT (si.ssa1); + // If defintion is in the same basic lock, evaluate it. + if (src && gimple_bb (src) == gimple_bb (stmt)) + gori_calc_operands (si.op1_range, src, r, q); + } + + if (si.ssa2 && !r.has_range (si.ssa2)) + { + tmp.set_type (TREE_TYPE (si.ssa2)); + if (si.calc_op2 (tmp, lhs, si.op1_range)) + si.op2_range.intersect (tmp); + r.set_range (si.ssa2, si.op2_range); + gimple *src = SSA_NAME_DEF_STMT (si.ssa2); + if (src && gimple_bb (src) == gimple_bb (stmt)) + gori_calc_operands (si.op2_range, src, r, q); + } +} + +// Use ssa_cache R as a repository for all outgoing ranges on edge E that +// can be calculated. Use OGR if present to establish starting edge ranges, +// and Q to resolve operand values. If Q is NULL use the current range +// query available to the system. + +bool +gori_on_edge (ssa_cache &r, edge e, range_query *q, gimple_outgoing_range *ogr) +{ + // Start with an empty vector + r.clear (); + int_range_max lhs; + // Determine if there is an outgoing edge. + gimple *stmt; + if (ogr) + stmt = ogr->edge_range_p (lhs, e); + else + { + stmt = gimple_outgoing_range_stmt_p (e->src); + if (stmt && is_a (stmt)) + gcond_edge_range (lhs, e); + else + stmt = NULL; + } + if (!stmt) + return false; + gori_calc_operands (lhs, stmt, r, q); + return true; +} + +// Helper for GORI_NAME_ON_EDGE which uses query Q to determine if STMT +// provides a range for NAME, and returns it in R if so. If it does not, +// continue processing feeding statments until we run out of statements +// or fine a range for NAME. + +bool +gori_name_helper (vrange &r, tree name, vrange &lhs, gimple *stmt, + range_query *q) +{ + struct gori_stmt_info si(lhs, stmt, q); + if (!si) + return false; + + if (si.ssa1 == name) + return si.calc_op1 (r, lhs, si.op2_range); + if (si.ssa2 == name) + return si.calc_op2 (r, lhs, si.op1_range); + + Value_Range tmp; + // Now evaluate operand ranges, and set them in the edge cache. + // If there was already a range, leave it and do no further evaluation. + if (si.ssa1) + { + tmp.set_type (TREE_TYPE (si.ssa1)); + if (si.calc_op1 (tmp, lhs, si.op2_range)) + si.op1_range.intersect (tmp); + gimple *src = SSA_NAME_DEF_STMT (si.ssa1); + // If defintion is in the same basic lock, evaluate it. + if (src && gimple_bb (src) == gimple_bb (stmt)) + if (gori_name_helper (r, name, si.op1_range, src, q)) + return true; + } + + if (si.ssa2) + { + tmp.set_type (TREE_TYPE (si.ssa2)); + if (si.calc_op2 (tmp, lhs, si.op1_range)) + si.op2_range.intersect (tmp); + gimple *src = SSA_NAME_DEF_STMT (si.ssa2); + if (src && gimple_bb (src) == gimple_bb (stmt)) + if (gori_name_helper (r, name, si.op2_range, src, q)) + return true; + } + return false; +} + +// Check if NAME has an outgoing range on edge E. Use query Q to evaluate +// the operands. Return TRUE and the range in R if there is an outgoing range. +// This is like gori_on_edge except it only looks for the single name and +// does not require an ssa_cache. + +bool +gori_name_on_edge (vrange &r, tree name, edge e, range_query *q) +{ + int_range_max lhs; + gimple *stmt = gimple_outgoing_range_stmt_p (e->src); + if (!stmt || !is_a (stmt)) + return false; + gcond_edge_range (lhs, e); + return gori_name_helper (r, name, lhs, stmt, q); +} diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h index b8d97d1dd72..e75ade03f5d 100644 --- a/gcc/gimple-range-gori.h +++ b/gcc/gimple-range-gori.h @@ -208,6 +208,21 @@ private: int m_not_executable_flag; }; +// These APIs are used to query GORI if there are ranges generated on an edge. +// GORI_ON_EDGE is used to get all the ranges at once (returned in an +// ssa_cache structure). +// GORI_NAME_ON_EDGE is used to simply ask if NAME has a range on edge E + +// Fill ssa-cache R with any outgoing ranges on edge E, using OGR and QUERY. +bool gori_on_edge (class ssa_cache &r, edge e, + range_query *query = NULL, + gimple_outgoing_range *ogr = NULL); + +// Query if NAME has an outgoing range on edge E, and return it in R if so. +// Note this doesnt use ranger, its a static GORI analysis of the range in +// block e->src and is based on any branch at the exit of that block. +bool gori_name_on_edge (vrange &r, tree name, edge e, range_query *q = NULL); + // For each name that is an import into BB's exports.. #define FOR_EACH_GORI_IMPORT_NAME(gori, bb, name) \ for (gori_export_iterator iter ((gori).imports ((bb))); \ -- 2.41.0