From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.223.131]) by sourceware.org (Postfix) with ESMTPS id 4B5FE3858415 for ; Fri, 5 Apr 2024 13:38:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 4B5FE3858415 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 4B5FE3858415 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=1712324294; cv=none; b=UqCHw9Ykm+isAUeztFlRIcKqGnqZTni/vGiBpg91z3grz+7nz5Qs05Uqm7SpkAkrSvUBch7fNFNu4w6nU/8P/yvny+tFnRmyxmU+3uMWiBSHmKw7BQq90hdBTRLB4H42m6z0/z0ZLQbKWPE0FW0auxpZFJ6kHz6Ca8KbeDlViAA= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1712324294; c=relaxed/simple; bh=r85U3JRNrNOqFEHehhrbu6b8Dbl1gKUG5yTvyztBsw8=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:Message-ID:MIME-Version; b=i3Blbum3FJQdoWeIjqJdprelOw965I3ZjuQzeXWPLdNF8DShhQsZM7zAe+5SPTo7D3LnAxeeEj9F+D8rFisQyVjd1LQzrSIPa53tqHvysL+GY4uyC2N3uOuQDXPCXT8t+Yk8V6MPaL9KY3FBlgKCissm4s3gJmR+gGgDqQ6C25k= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from [10.168.5.241] (unknown [10.168.5.241]) (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 488C51F7B4; Fri, 5 Apr 2024 13:38:11 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1712324291; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=qtKSpfQn+BVFOQaY+cuYiWhPFv7vZNuU3/2jsMFkelA=; b=LgQQHmf+ad4VzrMjZhECbd6YPbTB/k49kqEf2U91lis2FBsLY303AHJTUnPveZvyoVZWwa 4Kx4MQk+z4UmzPYouSna9Nq1bP58aaGBR47H5GRo3zPVlwsTKnh1UUfInvIgfIcRnoN3NU BDfDhdbICtpYCUzyOSlQT3x51Ll20i4= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1712324291; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=qtKSpfQn+BVFOQaY+cuYiWhPFv7vZNuU3/2jsMFkelA=; b=BzsgXUDZkQcSJB4vx9tfoXe4pWam1bBTzEUTij0JH1WtzeKq/nec2WUrCjWi/tQ+xfdVXB tLmJzO7c2i3tWwBg== Authentication-Results: smtp-out2.suse.de; none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1712324291; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=qtKSpfQn+BVFOQaY+cuYiWhPFv7vZNuU3/2jsMFkelA=; b=LgQQHmf+ad4VzrMjZhECbd6YPbTB/k49kqEf2U91lis2FBsLY303AHJTUnPveZvyoVZWwa 4Kx4MQk+z4UmzPYouSna9Nq1bP58aaGBR47H5GRo3zPVlwsTKnh1UUfInvIgfIcRnoN3NU BDfDhdbICtpYCUzyOSlQT3x51Ll20i4= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1712324291; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=qtKSpfQn+BVFOQaY+cuYiWhPFv7vZNuU3/2jsMFkelA=; b=BzsgXUDZkQcSJB4vx9tfoXe4pWam1bBTzEUTij0JH1WtzeKq/nec2WUrCjWi/tQ+xfdVXB tLmJzO7c2i3tWwBg== Date: Fri, 5 Apr 2024 15:38:11 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: Jan Hubicka Subject: Re: [PATCH 3/3] tree-optimization/114052 - niter analysis from undefined behavior Message-ID: <730q3nr0-0r40-6088-4p76-r40sp3q3q335@fhfr.qr> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Score: -3.29 X-Spam-Level: X-Spamd-Result: default: False [-3.29 / 50.00]; BAYES_HAM(-3.00)[100.00%]; FAKE_REPLY(1.00)[]; NEURAL_HAM_LONG(-1.00)[-1.000]; NEURAL_HAM_SHORT(-0.19)[-0.968]; MIME_GOOD(-0.10)[text/plain]; ARC_NA(0.00)[]; FROM_HAS_DN(0.00)[]; MIME_TRACE(0.00)[0:+]; MISSING_XM_UA(0.00)[]; RCVD_COUNT_ZERO(0.00)[0]; RCPT_COUNT_TWO(0.00)[2]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; FROM_EQ_ENVFROM(0.00)[]; TO_DN_SOME(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; FUZZY_BLOCKED(0.00)[rspamd.com]; DBL_BLOCKED_OPENRESOLVER(0.00)[tree-ssa-loop-niter.cc:url,suse.de:email] X-Spam-Status: No, score=-10.9 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 List-Id: On Fri, 5 Apr 2024, Richard Biener wrote: > 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. It FAILs FAIL: gcc.dg/pr53265.c at line 91 (test for warnings, line 90) FAIL: gcc.dg/pr53265.c at line 92 (test for warnings, line 90) for diagnostic purposes we'd need to treat the call as not terminating FAIL: gcc.dg/tree-ssa/cunroll-10.c scan-tree-dump-times cunroll "Forced statement unreachable" 2 FAIL: gcc.dg/tree-ssa/cunroll-11.c scan-tree-dump cunroll "Loop 1 iterates at most 3 times" FAIL: gcc.dg/tree-ssa/cunroll-9.c scan-tree-dump-times cunrolli "Removed pointless exit:" 1 FAIL: gcc.dg/tree-ssa/loop-38.c scan-tree-dump cunrolli "Loop 1 iterates at most 11 times" FAIL: gcc.dg/tree-ssa/pr68234.c scan-tree-dump vrp2 ">> 6" FAIL: c-c++-common/ubsan/unreachable-3.c -O0 scan-tree-dump optimized "__builtin___ubsan_handle_builtin_unreachable" ... FAIL: c-c++-common/ubsan/unreachable-3.c -Os scan-tree-dump optimized "__builtin___ubsan_handle_builtin_unreachable" > 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) > -- Richard Biener SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)