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 From patchwork Thu Oct 5 19:04:45 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1844131 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=QgAAbScX; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; 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 [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 ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4S1gwz5Tqrz1yq9 for ; Fri, 6 Oct 2023 06:05:07 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 80B473858401 for ; Thu, 5 Oct 2023 19:05:01 +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 C099A3858C5F for ; Thu, 5 Oct 2023 19:04:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org C099A3858C5F 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=1696532687; 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=tV9KqCbjLgU/sk0rUFcqEKLAb5iWk7fmUp2uJOZSzg0=; b=QgAAbScXMvGk0NFO/Fu2Sex1MK/Gm9GRl1O/b7UxIVOvs8EejtDlgt7CiYvnVBZ+aNBzQN bpeSzMw3nHNQTbURuGWkm+trr6ftIleId7ClIwAQcNhLjUkVZApe/aAQecXvx9qnil4pEg AHq6sRsqEuA+X3/yfa4tzkpT7snbOkk= Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-618-C8cVV3qQOjCNR6RhcL9b0Q-1; Thu, 05 Oct 2023 15:04:45 -0400 X-MC-Unique: C8cVV3qQOjCNR6RhcL9b0Q-1 Received: by mail-qv1-f72.google.com with SMTP id 6a1803df08f44-65b0d478deaso12831206d6.2 for ; Thu, 05 Oct 2023 12:04:45 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696532684; x=1697137484; 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=6a4QN79fG24xgVpSH4QgkEr17EKa+svliYQu29U81D4=; b=sHu6IDHNGsIcA4LECz8GQc/d+YpWSGyLRN9vQ0avlgv75oD0QM4oGatWLsvKV0AGoV NtS4mcNqcZHiqnxRbE4t2/MUe2VDdCkc7ctLdLaktJeJ503tucVqA0eW+SUdEs0xmrOW Dx5MKpEWKeT1eqKIFPtfBp0q02vYjRgJ6IozpPeprQQA6/WErzZDyQQ3MOWXOOr+3PCm 8D4/2MvIHyidbd0H99b354adCr8vg2b/1Dhdfe7uh1MXfOuB5kWmruThq9d6PnKOaKZF dkaEwg9oslV6RtdQvNQpNZMIRPRpR/bu9IoQ795PjJVAf6Xe4wc1JsZcvuBLGH2l9isQ I/cg== X-Gm-Message-State: AOJu0YwNijkeX/OYYI6sDnJ/aXUZs9FDMx5llRs8FeGDF7WqlJaS5yHP DFtSqgKNPi7CzJfUozK97NCEr5nGUGIiF5sXi2Y5RtehtkM++aM9u57OxzYxs9vtezAjIimK2El /ai7kPjFaQgj22bBP8qnCTZmCkHIhAayU+HXB9V4jwMY9X72enN1QjsCD9vchqlgzG3d1jDAny1 MMRw== X-Received: by 2002:a0c:ef0d:0:b0:653:5bed:83d4 with SMTP id t13-20020a0cef0d000000b006535bed83d4mr5778145qvr.30.1696532684638; Thu, 05 Oct 2023 12:04:44 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHaCuwPvQDegdvPvljGy3fReJMJfThDpEDRdWf2skqt2lkdJPcJKdDpUNHnsZ73xS6BMUPunQ== X-Received: by 2002:a0c:ef0d:0:b0:653:5bed:83d4 with SMTP id t13-20020a0cef0d000000b006535bed83d4mr5778116qvr.30.1696532684169; Thu, 05 Oct 2023 12:04:44 -0700 (PDT) Received: from [192.168.0.174] ([104.219.124.252]) by smtp.gmail.com with ESMTPSA id u14-20020a0cf1ce000000b006560eea8a7esm708610qvl.132.2023.10.05.12.04.43 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 05 Oct 2023 12:04:43 -0700 (PDT) Message-ID: Date: Thu, 5 Oct 2023 15:04:45 -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 2/3] Add a dom based ranger for fast VRP. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_ASCII_DIVIDERS, 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 a DOM based ranger that is intended to be used by a dom walk pass and provides basic ranges. It utilizes the new GORI edge API to find outgoing ranges on edges, and combines these with any ranges calculated during the walk up to this point.  When a query is made for a range not defined in the current block, a quick dom walk is performed looking for a range either on a single-pred  incoming  edge or defined in the block. Its about twice the speed of current EVRP, and although there is a bit of room to improve both memory usage and speed, I'll leave that until I either get around to it or we elect to use it and it becomes more important.   It also serves as a POC for anyone wanting to use the new GORI API to use edge ranges, as well as a potentially different fast VRP more similar to the old EVRP. This version performs more folding of PHI nodes as it has all the info on incoming edges, but at a slight cost, mostly memory.  It does no relation processing as yet. It has been bootstrapped running right after EVRP, and as a replacement for EVRP, and since it uses existing machinery, should be reasonably solid.   It is currently not invoked from anywhere. Pushed. Andrew From ad8cd713b4e489826e289551b8b8f8f708293a5b Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Fri, 28 Jul 2023 13:18:15 -0400 Subject: [PATCH 2/3] Add a dom based ranger for fast VRP. Provide a dominator based implementation of a range query. * gimple_range.cc (dom_ranger::dom_ranger): New. (dom_ranger::~dom_ranger): New. (dom_ranger::range_of_expr): New. (dom_ranger::edge_range): New. (dom_ranger::range_on_edge): New. (dom_ranger::range_in_bb): New. (dom_ranger::range_of_stmt): New. (dom_ranger::maybe_push_edge): New. (dom_ranger::pre_bb): New. (dom_ranger::post_bb): New. * gimple-range.h (class dom_ranger): New. --- gcc/gimple-range.cc | 300 ++++++++++++++++++++++++++++++++++++++++++++ gcc/gimple-range.h | 28 +++++ 2 files changed, 328 insertions(+) diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 13c3308d537..5e9bb397a20 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -928,3 +928,303 @@ assume_query::dump (FILE *f) } fprintf (f, "------------------------------\n"); } + +// --------------------------------------------------------------------------- + + +// Create a DOM based ranger for use by a DOM walk pass. + +dom_ranger::dom_ranger () : m_global (), m_out () +{ + m_freelist.create (0); + m_freelist.truncate (0); + m_e0.create (0); + m_e0.safe_grow_cleared (last_basic_block_for_fn (cfun)); + m_e1.create (0); + m_e1.safe_grow_cleared (last_basic_block_for_fn (cfun)); + m_pop_list = BITMAP_ALLOC (NULL); + if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE)) + tracer.enable_trace (); +} + +// Dispose of a DOM ranger. + +dom_ranger::~dom_ranger () +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Non-varying global ranges:\n"); + fprintf (dump_file, "=========================:\n"); + m_global.dump (dump_file); + } + BITMAP_FREE (m_pop_list); + m_e1.release (); + m_e0.release (); + m_freelist.release (); +} + +// Implement range of EXPR on stmt S, and return it in R. +// Return false if no range can be calculated. + +bool +dom_ranger::range_of_expr (vrange &r, tree expr, gimple *s) +{ + unsigned idx; + if (!gimple_range_ssa_p (expr)) + return get_tree_range (r, expr, s); + + if ((idx = tracer.header ("range_of_expr "))) + { + print_generic_expr (dump_file, expr, TDF_SLIM); + if (s) + { + fprintf (dump_file, " at "); + print_gimple_stmt (dump_file, s, 0, TDF_SLIM); + } + else + fprintf (dump_file, "\n"); + } + + if (s) + range_in_bb (r, gimple_bb (s), expr); + else + m_global.range_of_expr (r, expr, s); + + if (idx) + tracer.trailer (idx, " ", true, expr, r); + return true; +} + + +// Return TRUE and the range if edge E has a range set for NAME in +// block E->src. + +bool +dom_ranger::edge_range (vrange &r, edge e, tree name) +{ + bool ret = false; + basic_block bb = e->src; + + // Check if BB has any outgoing ranges on edge E. + ssa_lazy_cache *out = NULL; + if (EDGE_SUCC (bb, 0) == e) + out = m_e0[bb->index]; + else if (EDGE_SUCC (bb, 1) == e) + out = m_e1[bb->index]; + + // If there is an edge vector and it has a range, pick it up. + if (out && out->has_range (name)) + ret = out->get_range (r, name); + + return ret; +} + + +// Return the range of EXPR on edge E in R. +// Return false if no range can be calculated. + +bool +dom_ranger::range_on_edge (vrange &r, edge e, tree expr) +{ + basic_block bb = e->src; + unsigned idx; + if ((idx = tracer.header ("range_on_edge "))) + { + fprintf (dump_file, "%d->%d for ",e->src->index, e->dest->index); + print_generic_expr (dump_file, expr, TDF_SLIM); + fputc ('\n',dump_file); + } + + if (!gimple_range_ssa_p (expr)) + return get_tree_range (r, expr, NULL); + + if (!edge_range (r, e, expr)) + range_in_bb (r, bb, expr); + + if (idx) + tracer.trailer (idx, " ", true, expr, r); + return true; +} + +// Return the range of NAME as it exists at the end of block BB in R. + +void +dom_ranger::range_in_bb (vrange &r, basic_block bb, tree name) +{ + basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name)); + // Loop through dominators until we get to the entry block, or we find + // either the defintion block for NAME, or a single pred edge with a range. + while (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)) + { + // If we hit the deifntion block, pick up the global value. + if (bb == def_bb) + { + m_global.range_of_expr (r, name); + return; + } + // If its a single pred, check the outgoing range of the edge. + if (EDGE_COUNT (bb->preds) == 1 + && edge_range (r, EDGE_PRED (bb, 0), name)) + return; + // Otherwise move up to the dominator, and check again. + bb = get_immediate_dominator (CDI_DOMINATORS, bb); + } + m_global.range_of_expr (r, name); +} + + +// Calculate the range of NAME, as the def of stmt S and return it in R. +// Return FALSE if no range cqn be calculated. +// Also set the global range for NAME as this should only be called within +// the def block during a DOM walk. +// Outgoing edges were pre-calculated, so when we establish a global defintion +// check if any outgoing edges hav ranges that can be combined with the +// global. + +bool +dom_ranger::range_of_stmt (vrange &r, gimple *s, tree name) +{ + unsigned idx; + bool ret; + if (!name) + name = gimple_range_ssa_p (gimple_get_lhs (s)); + + gcc_checking_assert (!name || name == gimple_get_lhs (s)); + + if ((idx = tracer.header ("range_of_stmt "))) + print_gimple_stmt (dump_file, s, 0, TDF_SLIM); + + // Its already been calculated. + if (name && m_global.has_range (name)) + { + ret = m_global.range_of_expr (r, name, s); + if (idx) + tracer.trailer (idx, " Already had value ", ret, name, r); + return ret; + } + + // If there is a new calculated range and it is not varying, set + // a global range. + ret = fold_range (r, s, this); + if (ret && name && m_global.merge_range (name, r) && !r.varying_p ()) + { + if (set_range_info (name, r) && dump_file) + { + fprintf (dump_file, "Global Exported: "); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " = "); + r.dump (dump_file); + fputc ('\n', dump_file); + } + basic_block bb = gimple_bb (s); + unsigned bbi = bb->index; + Value_Range vr (TREE_TYPE (name)); + // If there is a range on edge 0, update it. + if (m_e0[bbi] && m_e0[bbi]->has_range (name)) + { + if (m_e0[bbi]->merge_range (name, r) && dump_file + && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Outgoing range for "); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " updated on edge %d->%d : ", bbi, + EDGE_SUCC (bb, 0)->dest->index); + if (m_e0[bbi]->get_range (vr, name)) + vr.dump (dump_file); + fputc ('\n', dump_file); + } + } + // If there is a range on edge 1, update it. + if (m_e1[bbi] && m_e1[bbi]->has_range (name)) + { + if (m_e1[bbi]->merge_range (name, r) && dump_file + && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Outgoing range for "); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " updated on edge %d->%d : ", bbi, + EDGE_SUCC (bb, 1)->dest->index); + if (m_e1[bbi]->get_range (vr, name)) + vr.dump (dump_file); + fputc ('\n', dump_file); + } + } + } + if (idx) + tracer.trailer (idx, " ", ret, name, r); + return ret; +} + +// Check if GORI has an ranges on edge E. If there re, store them in +// either the E0 or E1 vector based on EDGE_0. +// If there are no ranges, put the empty lazy_cache entry on the freelist +// for use next time. + +void +dom_ranger::maybe_push_edge (edge e, bool edge_0) +{ + ssa_lazy_cache *e_cache; + if (!m_freelist.is_empty ()) + e_cache = m_freelist.pop (); + else + e_cache = new ssa_lazy_cache; + gori_on_edge (*e_cache, e, this, &m_out); + if (e_cache->empty_p ()) + m_freelist.safe_push (e_cache); + else + { + if (edge_0) + m_e0[e->src->index] = e_cache; + else + m_e1[e->src->index] = e_cache; + } +} + +// Preprocess block BB. If there are any outgoing edges, precalculate +// the outgoing ranges and store them. Note these are done before +// we process the block, so global values have not been set yet. +// These are "pure" outgoing ranges inflicted by the condition. + +void +dom_ranger::pre_bb (basic_block bb) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "#FVRP entering BB %d\n", bb->index); + + // Next, see if this block needs outgoing edges calculated. + gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb); + if (!gsi_end_p (gsi)) + { + gimple *s = gsi_stmt (gsi); + if (is_a (s) && gimple_range_op_handler::supported_p (s)) + { + maybe_push_edge (EDGE_SUCC (bb, 0), true); + maybe_push_edge (EDGE_SUCC (bb, 1), false); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + if (m_e0[bb->index]) + { + fprintf (dump_file, "\nEdge ranges BB %d->%d\n", + bb->index, EDGE_SUCC (bb, 0)->dest->index); + m_e0[bb->index]->dump(dump_file); + } + if (m_e1[bb->index]) + { + fprintf (dump_file, "\nEdge ranges BB %d->%d\n", + bb->index, EDGE_SUCC (bb, 1)->dest->index); + m_e1[bb->index]->dump(dump_file); + } + } + } + } + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "#FVRP DONE entering BB %d\n", bb->index); +} + +// Perform any post block processing. + +void +dom_ranger::post_bb (basic_block) +{ +} diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index 6587e4923ff..5807a2b80e5 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -101,5 +101,33 @@ protected: gori_compute m_gori; }; +// DOM based ranger for fast VRP. +// This must be processed in DOM order, and does only basic range operations. +class dom_ranger : public range_query +{ +public: + dom_ranger (); + ~dom_ranger (); + + virtual bool range_of_expr (vrange &r, tree expr, gimple *s = NULL) override; + virtual bool range_on_edge (vrange &r, edge e, tree expr) override; + virtual bool range_of_stmt (vrange &r, gimple *s, tree name = NULL) override; + + bool edge_range (vrange &r, edge e, tree name); + void range_in_bb (vrange &r, basic_block bb, tree name); + + void pre_bb (basic_block bb); + void post_bb (basic_block bb); +protected: + DISABLE_COPY_AND_ASSIGN (dom_ranger); + void maybe_push_edge (edge e, bool edge_0); + ssa_cache m_global; + gimple_outgoing_range m_out; + vec m_freelist; + vec m_e0; + vec m_e1; + bitmap m_pop_list; + range_tracer tracer; +}; #endif // GCC_GIMPLE_RANGE_H -- 2.41.0 From patchwork Thu Oct 5 19:04:58 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1844132 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=OVLpI/7u; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; 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 [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 ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4S1gx61q89z1yq9 for ; Fri, 6 Oct 2023 06:05:14 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 39ED73860765 for ; Thu, 5 Oct 2023 19:05:12 +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.129.124]) by sourceware.org (Postfix) with ESMTPS id EB1B53856DDA for ; Thu, 5 Oct 2023 19:04:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org EB1B53856DDA 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=1696532699; 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=yh2L202qALIrKlaJgC7KPu/gld39UoWNjtFfzXUPaoM=; b=OVLpI/7uhasp66k/OPcchROqCBoTAn2c6e0m2KLkK/ZmaZaqqJh1nzx2n1nQtr0kQFZXWd UHBDQI2IfDXzIJ+GFywKoPsT2b4RVBqm1VZtE9nl1qYlse2HhQwHw6TGoCuR9ksuocO4zQ GHuBXQKgeKiIgUu22KGLTQMci4Y9XP0= Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-147-_O5xlP5pNUy8lE1iGUmpYw-1; Thu, 05 Oct 2023 15:04:58 -0400 X-MC-Unique: _O5xlP5pNUy8lE1iGUmpYw-1 Received: by mail-qv1-f72.google.com with SMTP id 6a1803df08f44-6557c921deeso11637076d6.2 for ; Thu, 05 Oct 2023 12:04:58 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696532697; x=1697137497; 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=n6LxkauqKcPjH4pZqjE6w5MEXel9T5MxP/sbFY/aZxY=; b=EvcLBw7MwYeWzo0KU3ePHNT4hwHeJo7J0HIIuDNs4fXed9EdaOfsNu4wwFOOfvtH87 kxBTD2tXEXacbjTWVtNUWb85Fb8h+opG+j5R7khlH2xdeAofKX0AtxXo7FvxLYeKBQw6 /I+iQl9xNaUJElRI+z5+lfUPkF7Co58e7TkFI30QdWK4h6BwMLF7ggdV6AsXh//6U6Wh sMLb5wSIfgm4wReEoZlvMlzp5BqsJN+tSVxo9mKB2sgzT0dU21cdcKR8jn3JtUfzrSG1 F8HW/OEm+mW8fmp6POY13D+zTKFVj08EKRCaF89eXVSRvIRS3F+IkipdlMWStCq8Eqpd IBMw== X-Gm-Message-State: AOJu0Yx3oe2l4xrdbc9gqTpbkkiZxEB2+ynfpI7meany63bvpSrD3NPe ZP4vIwl2k6hPxYg54JQXRCg4mDxP2D9Av3mbLpAFzbryRHI+3SIklHGOnz/1fkvAoNLkO+lk0sH e6M9r0hT74iOUkH4SO4Z5QuB7oJ0pwpPZePy8UAC5BYCjfvopoxJHudLNgL3Fogxj6B7fPDyrvv 0Yxg== X-Received: by 2002:a0c:e308:0:b0:635:e0dd:db4b with SMTP id s8-20020a0ce308000000b00635e0dddb4bmr6003013qvl.37.1696532697234; Thu, 05 Oct 2023 12:04:57 -0700 (PDT) X-Google-Smtp-Source: AGHT+IG7ZF0ul9D3YjjhU63afl4yo/FLUywIMamIp7KoH85uFE+pcOVsoigQV8blE6U3fuw12Qgw4Q== X-Received: by 2002:a0c:e308:0:b0:635:e0dd:db4b with SMTP id s8-20020a0ce308000000b00635e0dddb4bmr6002992qvl.37.1696532696887; Thu, 05 Oct 2023 12:04:56 -0700 (PDT) Received: from [192.168.0.174] ([104.219.124.252]) by smtp.gmail.com with ESMTPSA id v18-20020a0ccd92000000b006583270ea64sm439899qvm.139.2023.10.05.12.04.56 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 05 Oct 2023 12:04:56 -0700 (PDT) Message-ID: Date: Thu, 5 Oct 2023 15:04:58 -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 3/3] Create a fast VRP pass X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-10.3 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H4, 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 a fast VRP pass.  It is not invoked from anywhere, so should cause no issues. If you want to utilize it, simply add a new pass, ie: it will generate a dump file with the extension .fvrp. pushed. From f4e2dac53fd62fbf2af95e0bf26d24e929fa1f66 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Mon, 2 Oct 2023 18:32:49 -0400 Subject: [PATCH 3/3] Create a fast VRP pass * timevar.def (TV_TREE_FAST_VRP): New. * tree-pass.h (make_pass_fast_vrp): New prototype. * tree-vrp.cc (class fvrp_folder): New. (fvrp_folder::fvrp_folder): New. (fvrp_folder::~fvrp_folder): New. (fvrp_folder::value_of_expr): New. (fvrp_folder::value_on_edge): New. (fvrp_folder::value_of_stmt): New. (fvrp_folder::pre_fold_bb): New. (fvrp_folder::post_fold_bb): New. (fvrp_folder::pre_fold_stmt): New. (fvrp_folder::fold_stmt): New. (execute_fast_vrp): New. (pass_data_fast_vrp): New. (pass_vrp:execute): Check for fast VRP pass. (make_pass_fast_vrp): New. --- gcc/timevar.def | 1 + gcc/tree-pass.h | 1 + gcc/tree-vrp.cc | 124 ++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 126 insertions(+) diff --git a/gcc/timevar.def b/gcc/timevar.def index 9523598f60e..d21b08c030d 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -160,6 +160,7 @@ DEFTIMEVAR (TV_TREE_TAIL_MERGE , "tree tail merge") DEFTIMEVAR (TV_TREE_VRP , "tree VRP") DEFTIMEVAR (TV_TREE_VRP_THREADER , "tree VRP threader") DEFTIMEVAR (TV_TREE_EARLY_VRP , "tree Early VRP") +DEFTIMEVAR (TV_TREE_FAST_VRP , "tree Fast VRP") DEFTIMEVAR (TV_TREE_COPY_PROP , "tree copy propagation") DEFTIMEVAR (TV_FIND_REFERENCED_VARS , "tree find ref. vars") DEFTIMEVAR (TV_TREE_PTA , "tree PTA") diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index eba2d54ac76..9c4b1e4185c 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -470,6 +470,7 @@ extern gimple_opt_pass *make_pass_check_data_deps (gcc::context *ctxt); extern gimple_opt_pass *make_pass_copy_prop (gcc::context *ctxt); extern gimple_opt_pass *make_pass_isolate_erroneous_paths (gcc::context *ctxt); extern gimple_opt_pass *make_pass_early_vrp (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_fast_vrp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_assumptions (gcc::context *ctxt); extern gimple_opt_pass *make_pass_uncprop (gcc::context *ctxt); diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc index 4f8c7745461..19d8f995d70 100644 --- a/gcc/tree-vrp.cc +++ b/gcc/tree-vrp.cc @@ -1092,6 +1092,106 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p, return 0; } +// Implement a Fast VRP folder. Not quite as effective but faster. + +class fvrp_folder : public substitute_and_fold_engine +{ +public: + fvrp_folder (dom_ranger *dr) : substitute_and_fold_engine (), + m_simplifier (dr) + { m_dom_ranger = dr; } + + ~fvrp_folder () { } + + tree value_of_expr (tree name, gimple *s = NULL) override + { + // Shortcircuit subst_and_fold callbacks for abnormal ssa_names. + if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) + return NULL; + return m_dom_ranger->value_of_expr (name, s); + } + + tree value_on_edge (edge e, tree name) override + { + // Shortcircuit subst_and_fold callbacks for abnormal ssa_names. + if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) + return NULL; + return m_dom_ranger->value_on_edge (e, name); + } + + tree value_of_stmt (gimple *s, tree name = NULL) override + { + // Shortcircuit subst_and_fold callbacks for abnormal ssa_names. + if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) + return NULL; + return m_dom_ranger->value_of_stmt (s, name); + } + + void pre_fold_bb (basic_block bb) override + { + m_dom_ranger->pre_bb (bb); + // Now process the PHIs in advance. + gphi_iterator psi = gsi_start_phis (bb); + for ( ; !gsi_end_p (psi); gsi_next (&psi)) + { + tree name = gimple_range_ssa_p (PHI_RESULT (psi.phi ())); + if (name) + { + Value_Range vr(TREE_TYPE (name)); + m_dom_ranger->range_of_stmt (vr, psi.phi (), name); + } + } + } + + void post_fold_bb (basic_block bb) override + { + m_dom_ranger->post_bb (bb); + } + + void pre_fold_stmt (gimple *s) override + { + // Ensure range_of_stmt has been called. + tree type = gimple_range_type (s); + if (type) + { + Value_Range vr(type); + m_dom_ranger->range_of_stmt (vr, s); + } + } + + bool fold_stmt (gimple_stmt_iterator *gsi) override + { + bool ret = m_simplifier.simplify (gsi); + if (!ret) + ret = ::fold_stmt (gsi, follow_single_use_edges); + return ret; + } + +private: + DISABLE_COPY_AND_ASSIGN (fvrp_folder); + simplify_using_ranges m_simplifier; + dom_ranger *m_dom_ranger; +}; + + +// Main entry point for a FAST VRP pass using a dom ranger. + +unsigned int +execute_fast_vrp (struct function *fun) +{ + calculate_dominance_info (CDI_DOMINATORS); + dom_ranger dr; + fvrp_folder folder (&dr); + + gcc_checking_assert (!fun->x_range_query); + fun->x_range_query = &dr; + + folder.substitute_and_fold (); + + fun->x_range_query = NULL; + return 0; +} + namespace { const pass_data pass_data_vrp = @@ -1120,6 +1220,20 @@ const pass_data pass_data_early_vrp = ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ), }; +const pass_data pass_data_fast_vrp = +{ + GIMPLE_PASS, /* type */ + "fvrp", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_TREE_FAST_VRP, /* tv_id */ + PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ), +}; + + class pass_vrp : public gimple_opt_pass { public: @@ -1139,6 +1253,10 @@ public: bool gate (function *) final override { return flag_tree_vrp != 0; } unsigned int execute (function *fun) final override { + // Check for fast vrp. + if (&data == &pass_data_fast_vrp) + return execute_fast_vrp (fun); + return execute_ranger_vrp (fun, warn_array_bounds_p, final_p); } @@ -1224,6 +1342,12 @@ make_pass_early_vrp (gcc::context *ctxt) return new pass_vrp (ctxt, pass_data_early_vrp, false); } +gimple_opt_pass * +make_pass_fast_vrp (gcc::context *ctxt) +{ + return new pass_vrp (ctxt, pass_data_fast_vrp, false); +} + gimple_opt_pass * make_pass_assumptions (gcc::context *ctx) { -- 2.41.0