From patchwork Fri Apr 5 13:12:49 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 88102 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E5E933844744 for ; Fri, 5 Apr 2024 13:13:35 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.223.131]) by sourceware.org (Postfix) with ESMTPS id 081FF3858431 for ; Fri, 5 Apr 2024 13:12:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 081FF3858431 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 081FF3858431 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.135.223.131 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1712322778; cv=none; b=MD5MCgTS2EYm/0KfDcnwVLcl5APX2aMdg2nAppCc5QGzUVeLHX+KkwKUOvnCuBpsByQI1Uc7PO1mS4kks+pzdthha60HEfBtf/SJ3Go59mcTlRU3+qvMUilel1erygFZhBiAJYiqKhGtiunR7Slqyvoviw23VVkJSNiQCJa6ZfU= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1712322778; c=relaxed/simple; bh=lTByuxMfXbZ7NdHg/NEv8h+Kj3af97TeBCQLrZcfqbg=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version:Message-Id; b=RAwYhUNihPb23cOBDl1tjPGJHHR35zUdDkb5lJEZcPgfiQxQlOmlLniS2R2NVz0uOpKdtFUG2Eo3YCj83un4qCHRI6Of6xv7I2f/xugwKb9mQVyfeedjaDOR7bb7TTtPGk3L+11LrdgbpCncqHGWcTzwBFT1RtM9dIPZjW/T/Ic= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from imap2.dmz-prg2.suse.org (imap2.dmz-prg2.suse.org [IPv6:2a07:de40:b281:104:10:150:64:98]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id BB4D01F7A0; Fri, 5 Apr 2024 13:12:49 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1712322769; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=eySkaaU+UxycnLpE7sIjpSyWFaVzW7M5KaBaRW8zQiw=; b=ik3HhIA8LMRMFHjdPABgMuz7yhJrfwhuhTxpvLSkjNB/ss91P55cwyJCnuOqnVixKcGh1j z8nrQ7G500CJeJwRxXLq3bTQ+ZL6g4BNCwGka57wr0tFbSlHoN2sMJQfco8lanMSf+ihaD nsEf9Mk9XgAjp+SgxrF2rV+5KvFCu2A= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1712322769; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=eySkaaU+UxycnLpE7sIjpSyWFaVzW7M5KaBaRW8zQiw=; b=6tNt5laj88sMw2+U5dTDZ7dazBTmKS76nfP8H0froUVe5CZP1M1i7U9IbTZ4NsvUdoEh3S hpFOBct8MGonBQDw== Authentication-Results: smtp-out2.suse.de; dkim=pass header.d=suse.de header.s=susede2_rsa header.b=ik3HhIA8; dkim=pass header.d=suse.de header.s=susede2_ed25519 header.b=6tNt5laj DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1712322769; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=eySkaaU+UxycnLpE7sIjpSyWFaVzW7M5KaBaRW8zQiw=; b=ik3HhIA8LMRMFHjdPABgMuz7yhJrfwhuhTxpvLSkjNB/ss91P55cwyJCnuOqnVixKcGh1j z8nrQ7G500CJeJwRxXLq3bTQ+ZL6g4BNCwGka57wr0tFbSlHoN2sMJQfco8lanMSf+ihaD nsEf9Mk9XgAjp+SgxrF2rV+5KvFCu2A= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1712322769; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=eySkaaU+UxycnLpE7sIjpSyWFaVzW7M5KaBaRW8zQiw=; b=6tNt5laj88sMw2+U5dTDZ7dazBTmKS76nfP8H0froUVe5CZP1M1i7U9IbTZ4NsvUdoEh3S hpFOBct8MGonBQDw== Received: from imap2.dmz-prg2.suse.org (localhost [127.0.0.1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by imap2.dmz-prg2.suse.org (Postfix) with ESMTPS id 8D3A8139F1; Fri, 5 Apr 2024 13:12:49 +0000 (UTC) Received: from dovecot-director2.suse.de ([2a07:de40:b281:106:10:150:64:167]) by imap2.dmz-prg2.suse.org with ESMTPSA id qjzPINH4D2ZXKAAAn2gu4w (envelope-from ); Fri, 05 Apr 2024 13:12:49 +0000 Date: Fri, 5 Apr 2024 15:12:49 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: Jan Hubicka Subject: [PATCH 1/3] Pass reliable down to infer_loop_bounds_from_array MIME-Version: 1.0 Message-Id: <20240405131249.8D3A8139F1@imap2.dmz-prg2.suse.org> X-Spam-Level: X-Spamd-Result: default: False [-1.52 / 50.00]; NEURAL_HAM_LONG(-1.00)[-1.000]; R_DKIM_ALLOW(-0.20)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; NEURAL_HAM_SHORT(-0.20)[-1.000]; MIME_GOOD(-0.10)[text/plain]; MX_GOOD(-0.01)[]; BAYES_HAM(-0.01)[46.19%]; ARC_NA(0.00)[]; RCVD_VIA_SMTP_AUTH(0.00)[]; FUZZY_BLOCKED(0.00)[rspamd.com]; TO_DN_SOME(0.00)[]; MIME_TRACE(0.00)[0:+]; MISSING_XM_UA(0.00)[]; RCVD_TLS_ALL(0.00)[]; SPAMHAUS_XBL(0.00)[2a07:de40:b281:104:10:150:64:98:from]; FROM_EQ_ENVFROM(0.00)[]; FROM_HAS_DN(0.00)[]; RCPT_COUNT_TWO(0.00)[2]; RCVD_COUNT_TWO(0.00)[2]; TO_MATCH_ENVRCPT_ALL(0.00)[]; DBL_BLOCKED_OPENRESOLVER(0.00)[imap2.dmz-prg2.suse.org:helo,imap2.dmz-prg2.suse.org:rdns,suse.de:dkim]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; DKIM_TRACE(0.00)[suse.de:+] X-Rspamd-Action: no action X-Rspamd-Queue-Id: BB4D01F7A0 X-Rspamd-Server: rspamd1.dmz-prg2.suse.org X-Spam-Score: -1.52 X-Spam-Status: No, score=-11.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, 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+patchwork=sourceware.org@gcc.gnu.org The following passes down whether a stmt is always executed from infer_loop_bounds_from_undefined to infer_loop_bounds_from_array. The parameters were already documented. The patch doesn't remove possibly redundant checks from idx_infer_loop_bounds yet. Boostrapped on x86_64-unknown-linux-gnu, testing in progress. * tree-ssa-loop-niter.cc (ilb_data::reliable): New. (idx_infer_loop_bounds): Initialize upper from reliable. (infer_loop_bounds_from_ref): Get and pass through reliable flag. (infer_loop_bounds_from_array): Likewise. (infer_loop_bounds_from_undefined): Pass reliable flag to infer_loop_bounds_from_array. --- gcc/tree-ssa-loop-niter.cc | 19 +++++++++++-------- 1 file changed, 11 insertions(+), 8 deletions(-) diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc index c6d010f6d89..0a77c1bb544 100644 --- a/gcc/tree-ssa-loop-niter.cc +++ b/gcc/tree-ssa-loop-niter.cc @@ -4123,6 +4123,7 @@ struct ilb_data { class loop *loop; gimple *stmt; + bool reliable; }; static bool @@ -4131,7 +4132,7 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta) struct ilb_data *data = (struct ilb_data *) dta; tree ev, init, step; tree low, high, type, next; - bool sign, upper = true, has_flexible_size = false; + bool sign, upper = data->reliable, has_flexible_size = false; class loop *loop = data->loop; if (TREE_CODE (base) != ARRAY_REF) @@ -4224,12 +4225,14 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta) STMT is guaranteed to be executed in every iteration of LOOP.*/ static void -infer_loop_bounds_from_ref (class loop *loop, gimple *stmt, tree ref) +infer_loop_bounds_from_ref (class loop *loop, gimple *stmt, tree ref, + bool reliable) { struct ilb_data data; data.loop = loop; data.stmt = stmt; + data.reliable = reliable; for_each_index (&ref, idx_infer_loop_bounds, &data); } @@ -4238,7 +4241,7 @@ infer_loop_bounds_from_ref (class loop *loop, gimple *stmt, tree ref) executed in every iteration of LOOP. */ static void -infer_loop_bounds_from_array (class loop *loop, gimple *stmt) +infer_loop_bounds_from_array (class loop *loop, gimple *stmt, bool reliable) { if (is_gimple_assign (stmt)) { @@ -4248,10 +4251,10 @@ infer_loop_bounds_from_array (class loop *loop, gimple *stmt) /* For each memory access, analyze its access function and record a bound on the loop iteration domain. */ if (REFERENCE_CLASS_P (op0)) - infer_loop_bounds_from_ref (loop, stmt, op0); + infer_loop_bounds_from_ref (loop, stmt, op0, reliable); if (REFERENCE_CLASS_P (op1)) - infer_loop_bounds_from_ref (loop, stmt, op1); + infer_loop_bounds_from_ref (loop, stmt, op1, reliable); } else if (is_gimple_call (stmt)) { @@ -4260,13 +4263,13 @@ infer_loop_bounds_from_array (class loop *loop, gimple *stmt) lhs = gimple_call_lhs (stmt); if (lhs && REFERENCE_CLASS_P (lhs)) - infer_loop_bounds_from_ref (loop, stmt, lhs); + infer_loop_bounds_from_ref (loop, stmt, lhs, reliable); for (i = 0; i < n; i++) { arg = gimple_call_arg (stmt, i); if (REFERENCE_CLASS_P (arg)) - infer_loop_bounds_from_ref (loop, stmt, arg); + infer_loop_bounds_from_ref (loop, stmt, arg, reliable); } } } @@ -4410,7 +4413,7 @@ infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs) { gimple *stmt = gsi_stmt (bsi); - infer_loop_bounds_from_array (loop, stmt); + infer_loop_bounds_from_array (loop, stmt, reliable); if (reliable) { From patchwork Fri Apr 5 13:13:10 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 88103 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C3228384646C for ; Fri, 5 Apr 2024 13:13:58 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.223.130]) by sourceware.org (Postfix) with ESMTPS id 1AA96384604F for ; Fri, 5 Apr 2024 13:13:16 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1AA96384604F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 1AA96384604F Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.135.223.130 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1712322798; cv=none; b=dmc3YvqFgDglhfmV1+dUPkmSrkqVqlsZwCtXHhygK/otIJ6RJnblOgn13DJVzI+4G/0p78qwTbS/EPYnAc7dJKBMpD9iC8gbCm6W5xMZvXyq84UtnZQf7TQTRBoJapQhnQ8HIv7Z1rficb4q4W52dZFyn/teDvV9/AsB3KMwDiA= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1712322798; c=relaxed/simple; bh=hOFeVA7xkIgncWzDgT7V/lp/AIedRHwQN9jl8dsB9k4=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version:Message-Id; b=DKxpr1cQJ7Xnyt5bYIYh5FTYBQ0guUoTrmDXfBgeA8P0unUm4SBFjqSSE8mXKRn065ewIoFmrq4dkfdRbFxDcxhiQXG9Sjtdiq1+/1hZ2R2vo9QcauMHLiGcvW8HAYkDr6tsG9SDp8kyZpDKjuY0wp/6I/md/XQFet3PofyUdIc= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from imap2.dmz-prg2.suse.org (imap2.dmz-prg2.suse.org [IPv6:2a07:de40:b281:104:10:150:64:98]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 099C021A3E; Fri, 5 Apr 2024 13:13:15 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1712322795; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=iO/mmzOJQH1qeVhFw/e3VcZ4yQjFDSL73JtAxaMaa2A=; b=u/g15qGMcaD3zx4kWnR+aYBWlzszhbAAOTqLulszAdH4dCRNGO8rJti9h/qWv6rODwmz08 8EIYWldW3M8qrxONNdzCG4SWpPC54HHmWaxpfLDsEmk5YbBxbdBqKyauWpk2j7vNtEHT9g 7EU3teeGjpOH7QkCOKH/pjpg5zl2HkE= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1712322795; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=iO/mmzOJQH1qeVhFw/e3VcZ4yQjFDSL73JtAxaMaa2A=; b=5G9g94EMXwTnqKJe8hLws/jFVsgWRygrF5Khm7DTvz4HVoJkdbvBWsnw+uTpV9YQNjGR43 XoVAY1L15H9Rd9Bw== Authentication-Results: smtp-out1.suse.de; dkim=pass header.d=suse.de header.s=susede2_rsa header.b="u/g15qGM"; dkim=pass header.d=suse.de header.s=susede2_ed25519 header.b=5G9g94EM DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1712322795; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=iO/mmzOJQH1qeVhFw/e3VcZ4yQjFDSL73JtAxaMaa2A=; b=u/g15qGMcaD3zx4kWnR+aYBWlzszhbAAOTqLulszAdH4dCRNGO8rJti9h/qWv6rODwmz08 8EIYWldW3M8qrxONNdzCG4SWpPC54HHmWaxpfLDsEmk5YbBxbdBqKyauWpk2j7vNtEHT9g 7EU3teeGjpOH7QkCOKH/pjpg5zl2HkE= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1712322795; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=iO/mmzOJQH1qeVhFw/e3VcZ4yQjFDSL73JtAxaMaa2A=; b=5G9g94EMXwTnqKJe8hLws/jFVsgWRygrF5Khm7DTvz4HVoJkdbvBWsnw+uTpV9YQNjGR43 XoVAY1L15H9Rd9Bw== Received: from imap2.dmz-prg2.suse.org (localhost [127.0.0.1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by imap2.dmz-prg2.suse.org (Postfix) with ESMTPS id DEC1A139F1; Fri, 5 Apr 2024 13:13:14 +0000 (UTC) Received: from dovecot-director2.suse.de ([2a07:de40:b281:106:10:150:64:167]) by imap2.dmz-prg2.suse.org with ESMTPSA id ICbCNOr4D2ZzKAAAn2gu4w (envelope-from ); Fri, 05 Apr 2024 13:13:14 +0000 Date: Fri, 5 Apr 2024 15:13:10 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: Jan Hubicka Subject: [PATCH 2/3] Add get_loop_body_in_rpo MIME-Version: 1.0 Message-Id: <20240405131314.DEC1A139F1@imap2.dmz-prg2.suse.org> X-Spam-Score: -4.51 X-Rspamd-Action: no action X-Rspamd-Queue-Id: 099C021A3E X-Spam-Level: X-Rspamd-Server: rspamd2.dmz-prg2.suse.org X-Spamd-Result: default: False [-4.51 / 50.00]; BAYES_HAM(-3.00)[100.00%]; NEURAL_HAM_LONG(-1.00)[-1.000]; R_DKIM_ALLOW(-0.20)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; NEURAL_HAM_SHORT(-0.20)[-1.000]; MIME_GOOD(-0.10)[text/plain]; MX_GOOD(-0.01)[]; RECEIVED_SPAMHAUS_BLOCKED_OPENRESOLVER(0.00)[2a07:de40:b281:106:10:150:64:167:received]; RBL_SPAMHAUS_BLOCKED_OPENRESOLVER(0.00)[2a07:de40:b281:104:10:150:64:98:from]; RCVD_VIA_SMTP_AUTH(0.00)[]; ARC_NA(0.00)[]; FUZZY_BLOCKED(0.00)[rspamd.com]; MIME_TRACE(0.00)[0:+]; MISSING_XM_UA(0.00)[]; RCVD_TLS_ALL(0.00)[]; RCPT_COUNT_TWO(0.00)[2]; TO_DN_SOME(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; FROM_HAS_DN(0.00)[]; DWL_DNSWL_BLOCKED(0.00)[suse.de:dkim]; RCVD_COUNT_TWO(0.00)[2]; TO_MATCH_ENVRCPT_ALL(0.00)[]; DBL_BLOCKED_OPENRESOLVER(0.00)[imap2.dmz-prg2.suse.org:helo,imap2.dmz-prg2.suse.org:rdns,suse.de:dkim]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; DKIM_TRACE(0.00)[suse.de:+] X-Spam-Status: No, score=-11.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, 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+patchwork=sourceware.org@gcc.gnu.org The following adds another get_loop_body variant, one to get blocks in RPO. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. * cfgloop.h (get_loop_body_in_rpo): Declare. * cfgloop.cc (get_loop_body_in_rpo): Compute loop body in RPO. --- gcc/cfgloop.cc | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++ gcc/cfgloop.h | 1 + 2 files changed, 69 insertions(+) diff --git a/gcc/cfgloop.cc b/gcc/cfgloop.cc index 5202c3865d1..d79a006554f 100644 --- a/gcc/cfgloop.cc +++ b/gcc/cfgloop.cc @@ -1021,6 +1021,74 @@ get_loop_body_in_bfs_order (const class loop *loop) return blocks; } +/* Get the body of LOOP in FN in reverse post order. */ + +basic_block * +get_loop_body_in_rpo (function *fn, const class loop *loop) +{ + auto_vec stack (loop->num_nodes + 1); + auto_bb_flag visited (fn); + + basic_block *blocks = XNEWVEC (basic_block, loop->num_nodes); + int rev_post_order_num = loop->num_nodes - 1; + + /* Find a block leading to the loop header. */ + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, loop->header->preds) + if (!flow_bb_inside_loop_p (loop, e->src)) + break; + basic_block preheader = e->src; + + stack.quick_push (ei_start (preheader->succs)); + + while (!stack.is_empty ()) + { + basic_block src; + basic_block dest; + + /* Look at the edge on the top of the stack. */ + edge_iterator ei = stack.last (); + src = ei_edge (ei)->src; + dest = ei_edge (ei)->dest; + + /* Check if the edge destination has been visited yet. */ + if (flow_bb_inside_loop_p (loop, dest) + && ! (dest->flags & visited)) + { + /* Mark that we have visited the destination. */ + dest->flags |= visited; + + if (EDGE_COUNT (dest->succs) > 0) + /* Since the DEST node has been visited for the first + time, check its successors. */ + stack.quick_push (ei_start (dest->succs)); + else + /* There are no successors for the DEST node so record + the block. */ + blocks[rev_post_order_num--] = dest; + } + else + { + if (ei_one_before_end_p (ei) + && src != preheader) + /* There are no more successors for the SRC node + so record the block. */ + blocks[rev_post_order_num--] = src; + + if (!ei_one_before_end_p (ei)) + ei_next (&stack.last ()); + else + stack.pop (); + } + } + + for (int i = rev_post_order_num + 1; i < (int) loop->num_nodes; ++i) + blocks[i]->flags &= ~visited; + + return blocks; +} + /* Hash function for struct loop_exit. */ hashval_t diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 30b5e40d0d9..42f3079102d 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -385,6 +385,7 @@ extern basic_block *get_loop_body_in_custom_order (const class loop *, int (*) (const void *, const void *)); extern basic_block *get_loop_body_in_custom_order (const class loop *, void *, int (*) (const void *, const void *, void *)); +extern basic_block *get_loop_body_in_rpo (function *, const class loop *); extern auto_vec get_loop_exit_edges (const class loop *, basic_block * = NULL); extern edge single_exit (const class loop *); From patchwork Fri Apr 5 13:13:34 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 88104 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 966DA384474D for ; Fri, 5 Apr 2024 13:15:00 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.223.130]) by sourceware.org (Postfix) with ESMTPS id DB0DF3844758 for ; Fri, 5 Apr 2024 13:13:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org DB0DF3844758 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org DB0DF3844758 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.135.223.130 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1712322819; cv=none; b=QMV3F7h+GON1JFDgoJr84lHZ28zdPrMPOLgZhrxEjQkdKEemomsb+TMJHyFpRrrBCP88IwbEaCWw2tuZq6aYzi1IeWbs4fwsW0ABVBus5HbWodIyB1f+3VBzN8k30W83MNTEKqbDDocRPw2cUk9GX1pwgrqEPw+bwJxoiGXSZEY= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1712322819; c=relaxed/simple; bh=G6hSAZfGx7VNriJAGKEc3DsQ4KRhQvkXiBWcFtiyQ2Q=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version:Message-Id; b=maNdJGY8UD7K+PSEz9Yq5ERCmd1RMoLRqZ3k5pFpB4qeXCc2AwrbvdcG9caFPpCi4b501+pEmbqAkdidVUEQhwkzTWzVwFql/VYiodNlBEsASFCLkOHfEufXS9vp/5wJCtUJRv4ln1k+Z06awuY9HBBBuoM1gT3M0NRw3UBYaZg= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from imap2.dmz-prg2.suse.org (imap2.dmz-prg2.suse.org [IPv6:2a07:de40:b281:104:10:150:64:98]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id A57E821A3F; Fri, 5 Apr 2024 13:13:34 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1712322815; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=pD/GVjKs/TfG36PcXvT0KtXVJLns0O313jMZiklN6Kk=; b=bS5Ae+0s6sv/ips+3Mc2dG9+q+XDhHCBCs/idleUOn7YZdVulmUiZg/ccLbOUsMi0kETPd 1tO48i5TUtrumSzYjH1ncEIbjVXuGKKRgV2mAjodMN8uvxz0UYRQN35Fd5aUzGELr+6nLn F/48bek5AVmuCCOJZqAppzv3tAkA5yE= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1712322815; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=pD/GVjKs/TfG36PcXvT0KtXVJLns0O313jMZiklN6Kk=; b=M5RZFnSlGfkoa3imNDKcf69mr+V0k+OnwEN1deZrq25iGWptNdTSgX6VrNM3WzTsaa7xcD 1t/CekmWAJNZCGAA== Authentication-Results: smtp-out1.suse.de; dkim=pass header.d=suse.de header.s=susede2_rsa header.b=xXd1i7Gk; dkim=pass header.d=suse.de header.s=susede2_ed25519 header.b=I7sekyVz DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1712322814; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=pD/GVjKs/TfG36PcXvT0KtXVJLns0O313jMZiklN6Kk=; b=xXd1i7GkFlwnMLnlCSru0OWFFFop3bhbw1gsslkAutpeDsoW33uyLyiKbVlEet2N3Y9mq1 NNxW/csKSHyI2328YkjjrZSxVJHF8PjFpWMC+1JpqmeoXM2qLfaAZKneNABore/enOSrbZ AzqchG0tEmdTkXEQ+TRFiDNhq2Ot27Q= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1712322814; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=pD/GVjKs/TfG36PcXvT0KtXVJLns0O313jMZiklN6Kk=; b=I7sekyVzdZVsRvz4FSDosb1QB+PlB7rEOPJZJCzCAnzrjGt5zF6Tt5CKf+8Utidz0H09QK nIQgzeC9EOpxNPDw== Received: from imap2.dmz-prg2.suse.org (localhost [127.0.0.1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by imap2.dmz-prg2.suse.org (Postfix) with ESMTPS id 85979139F1; Fri, 5 Apr 2024 13:13:34 +0000 (UTC) Received: from dovecot-director2.suse.de ([2a07:de40:b281:106:10:150:64:167]) by imap2.dmz-prg2.suse.org with ESMTPSA id unAAH/74D2aQKAAAn2gu4w (envelope-from ); Fri, 05 Apr 2024 13:13:34 +0000 Date: Fri, 5 Apr 2024 15:13:34 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: Jan Hubicka Subject: [PATCH 3/3] tree-optimization/114052 - niter analysis from undefined behavior MIME-Version: 1.0 Message-Id: <20240405131334.85979139F1@imap2.dmz-prg2.suse.org> X-Spam-Score: -4.51 X-Rspamd-Action: no action X-Rspamd-Queue-Id: A57E821A3F X-Spam-Level: X-Rspamd-Server: rspamd2.dmz-prg2.suse.org X-Spamd-Result: default: False [-4.51 / 50.00]; BAYES_HAM(-3.00)[100.00%]; NEURAL_HAM_LONG(-1.00)[-1.000]; R_DKIM_ALLOW(-0.20)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; NEURAL_HAM_SHORT(-0.20)[-1.000]; MIME_GOOD(-0.10)[text/plain]; MX_GOOD(-0.01)[]; RECEIVED_SPAMHAUS_BLOCKED_OPENRESOLVER(0.00)[2a07:de40:b281:106:10:150:64:167:received]; RBL_SPAMHAUS_BLOCKED_OPENRESOLVER(0.00)[2a07:de40:b281:104:10:150:64:98:from]; RCVD_VIA_SMTP_AUTH(0.00)[]; ARC_NA(0.00)[]; FUZZY_BLOCKED(0.00)[rspamd.com]; MIME_TRACE(0.00)[0:+]; MISSING_XM_UA(0.00)[]; RCVD_TLS_ALL(0.00)[]; RCPT_COUNT_TWO(0.00)[2]; TO_DN_SOME(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; FROM_HAS_DN(0.00)[]; DWL_DNSWL_BLOCKED(0.00)[suse.de:dkim]; RCVD_COUNT_TWO(0.00)[2]; TO_MATCH_ENVRCPT_ALL(0.00)[]; DBL_BLOCKED_OPENRESOLVER(0.00)[tree-ssa-loop-niter.cc:url,imap2.dmz-prg2.suse.org:helo,imap2.dmz-prg2.suse.org:rdns,suse.de:dkim]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; DKIM_TRACE(0.00)[suse.de:+] X-Spam-Status: No, score=-11.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, 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+patchwork=sourceware.org@gcc.gnu.org The following makes sure to only compute upper bounds for the number of iterations of loops from undefined behavior invoked by stmts when those are executed in each loop iteration, in particular also in the last one. The latter cannot be guaranteed if there's possible infinite loops or calls with side-effects possibly executed before the stmt. Rather than adjusting the bound by one or using the bound as estimate the following for now gives up. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. PR tree-optimization/114052 * tree-ssa-loop-niter.cc (infer_loop_bounds_from_undefined): When we enter a possibly infinite loop or when we come across a call with side-effects record the last iteration might not execute all stmts. Consider bounds as unreliable in that case. * gcc.dg/tree-ssa/pr114052-1.c: New testcase. --- gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c | 16 ++++++++++ gcc/tree-ssa-loop-niter.cc | 35 ++++++++++++++++++---- 2 files changed, 45 insertions(+), 6 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c new file mode 100644 index 00000000000..54a2181e67e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo(void) +{ + int counter = 0; + while (1) + { + if (counter >= 2) + continue; + __builtin_printf("%i\n", counter++); + } + return 0; +} + +/* { dg-final { scan-tree-dump-not "unreachable" "optimized" } } */ diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc index 0a77c1bb544..52a39eb3500 100644 --- a/gcc/tree-ssa-loop-niter.cc +++ b/gcc/tree-ssa-loop-niter.cc @@ -4397,7 +4397,7 @@ infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs) unsigned i; gimple_stmt_iterator bsi; basic_block bb; - bool reliable; + bool may_have_exited = false; for (i = 0; i < loop->num_nodes; i++) { @@ -4407,21 +4407,44 @@ infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs) use the operations in it to infer reliable upper bound on the # of iterations of the loop. However, we can use it as a guess. Reliable guesses come only from array bounds. */ - reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb); + bool reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb); + + /* A possibly infinite inner loop makes further blocks not always + executed. Key on the entry of such a loop as that avoids RPO + issues with where the exits of that loop are. Any block + inside an irreducible sub-region is problematic as well. + ??? Note this technically only makes the last iteration + possibly partially executed. */ + if (!may_have_exited + && bb != loop->header + && (!loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) + || bb->flags & BB_IRREDUCIBLE_LOOP + || (bb->loop_father->header == bb + && !finite_loop_p (bb->loop_father)))) + may_have_exited = true; for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) { gimple *stmt = gsi_stmt (bsi); - infer_loop_bounds_from_array (loop, stmt, reliable); + /* When there's a call that might not return the last iteration + is possibly partial. This matches what we check in invariant + motion. + ??? For the call argument evaluation it would be still OK. */ + if (!may_have_exited + && is_gimple_call (stmt) + && gimple_has_side_effects (stmt)) + may_have_exited = true; + + infer_loop_bounds_from_array (loop, stmt, + reliable && !may_have_exited); - if (reliable) + if (reliable && !may_have_exited) { infer_loop_bounds_from_signedness (loop, stmt); infer_loop_bounds_from_pointer_arith (loop, stmt); } } - } } @@ -4832,7 +4855,7 @@ estimate_numbers_of_iterations (class loop *loop) diagnose those loops with -Waggressive-loop-optimizations. */ number_of_latch_executions (loop); - basic_block *body = get_loop_body (loop); + basic_block *body = get_loop_body_in_rpo (cfun, loop); auto_vec exits = get_loop_exit_edges (loop, body); likely_exit = single_likely_exit (loop, exits); FOR_EACH_VEC_ELT (exits, i, ex)