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)