From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from www523.your-server.de (www523.your-server.de [159.69.224.22]) by sourceware.org (Postfix) with ESMTPS id 4C0913857034 for ; Thu, 9 Jun 2022 14:50:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4C0913857034 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tim-lange.me Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tim-lange.me DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tim-lange.me; s=default2108; h=Content-Type:MIME-Version:Message-Id:To: Subject:From:Date:Sender:Reply-To:Cc:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:In-Reply-To:References; bh=PGwJ3b39F/GuR/iD4MCA2KudOSg3K/WjBImxX7VyoDg=; b=lEAJWaCawf987PPQBzLbajdYo0 vW/gROoF+zT4R4sEG1a0PWM7Xb/BrBYK2PTkmjXHf/HlEBi6tM35iDkZrZjQOAHA26Bbe2IgZa0xE VSBfTZgEXwUif8NeJLkKdn0hUy2CTJjccqif38Pvo/J7rPbwLg3/W0OjnTdBBKNRHHMgG3VRKozBb +s1gYMdliDtgp3GnKZhO17oHqcwd25cxRW0CCVTlA/XjZlmrk3hKhHo7GMOuyOa6nC2vDrz0cVgVh AmlwQQ5bZx5OnJWTfL/jZPSKm8NYrfrufRHMHd6I0pvuYlAP3y4UGMkd8Or2Ds3+2w1RisiKBdJEe z6gHfjuQ==; Received: from sslproxy04.your-server.de ([78.46.152.42]) by www523.your-server.de with esmtpsa (TLSv1.3:TLS_AES_256_GCM_SHA384:256) (Exim 4.92.3) (envelope-from ) id 1nzJTz-0009Dk-Mq; Thu, 09 Jun 2022 16:49:59 +0200 Received: from [2a02:908:1864:dbe0::4d53] (helo=fedora) by sslproxy04.your-server.de with esmtpsa (TLSv1.3:TLS_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1nzJTz-000HBC-I0; Thu, 09 Jun 2022 16:49:59 +0200 Date: Thu, 09 Jun 2022 16:49:53 +0200 From: Tim Lange Subject: fanalyzer: debugging zero state machine To: dmalcolm@redhat.com, GCC Mailing List Message-Id: <57T7DR.KTUNZBPTS69U1@tim-lange.me> X-Mailer: geary/40.0 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed X-Authenticated-Sender: mail@tim-lange.me X-Virus-Scanned: Clear (ClamAV 0.103.6/26567/Thu Jun 9 10:06:06 2022) X-Spam-Status: No, score=-1.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, KAM_INFOUSMEBIZ, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=no 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@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 09 Jun 2022 14:50:03 -0000 > On Mi, Jun 8 2022 at 11:12:52 -0400, David Malcolm wrote: > > On Wed, 2022-06-08 at 01:42 +0200, Tim Lange wrote: > > > > Hi Dave, > > > > I did spent some time to think about the zero state machine. I first > > thought about distinguishing between "assigned zero" and "EQ 0 > > condition on the path" for cases where e.g. unreachable() is used to > > say that some variable will never be zero according to the programmer. > > In that case the dev might not want zero warnings from conditions > > outside the if body itself for dev build where unreachable expands to > > some panic exit. But as the condition constraint is not pruned when the > > state machine is distinguishing the states, I'm not sure how to know > > whether the analysis already left the if body? > > The analyzer works on the gimple-ssa representation, which uses basic > blocks in a CFG, rather than an AST, so the only remants we have of > scope is in "clobber" statements (a special kind of assignment stmt), > which the gimplify adds as variables go out of scope. If the constraints only lived until the immediate dominator of `if (cond)`, I could easily distinguish: 1. if (x == 0) && still inside the if => zero 2. if (x == 0) && outside if => maybe zero but as this seems to be not the case, if I want to distinguish 1. & 2., I'd have to find another way. > > For pruning, the analyzer's state_machine class has a "can_purge_p" > virtual function: > > /* Return true if it safe to discard the given state (to help > when simplifying state objects). > States that need leak detection should return false. */ > virtual bool can_purge_p (state_t s) const = 0; > > which should return true for a "zeroness" state machine, in that we > always consider pruning states for svalues that aren't needed anymore > along a path. Is implemented and returns true. > > Is there some other kind of state explosion you're running into? It's > hard to figure this out further without seeing code. No, my code is by far not that mature to be tested. I just had in my head that I wanted to find out if I can distinguish the two cases. > > > > Also, while trying out different things, it seems simple assignments on > > phi like here > > int x; > > if (argc == 1) { > > x = 1; // x_5 > > } else { > > x = 0; // x_4 > > } > > printf("%i", 5 / x); // x_2 > > automatically work such that x_2 already inherits the state from > > x_4/x_5 without me doing anything inside my sm's on_phi function. Same > > for the simple y = 0; x = y; case. Where does this happen inside the > > code? > > With the caveat that I'm seeing your code, what's probably happening is > that we have either: > > BB (a): > x_5 = 1; > goto BB (c); > > BB (b): > x_4 = 0; > goto BB (c); > > BB (c): > x_2 = PHI (x_5 from (a), x_4 from (b)); I compiled it with -g, so this one is like the dumped gimple. > > or (at higher optimization levels): > > BB (a): > goto BB (c); > > BB (b): > goto BB (c); > > BB (c): > x_2 = PHI (1 from (a), 0 from (b)); > > and I think that at the phi node we have region_model::handle_phi, > which is setting x_2 to either the constant 1 or the constant 0 in the > store, and is calling the on_phi vfunc, leading to on_phi being called > for all state machines. Thanks, that is the case. The set_value inside handle_phi seems to this for me. > > BTW, are you implementing an override for this vfunc: > virtual state_machine::state_t get_default_state (const svalue *) > const; > > to capture the inherently known zeroness/nonzeroness of constant_svalue > instances? That would make those constants have that state. Yeah, I saw that on your nullness check. I tried it on a small example with and without, but didn't noticed a difference in warnings (except for not having zero(x_4) inside the supergraph.dot). So if I understood this right, this is just to have one state less for that variable/value[0]? If that is right, is it also favorable to "merge" the stop state and non_zero state inside the zero state machine because - for now - there is no warning planned on non-zero values? [0] less states are favorable because then the analyzer maybe has less different enodes to visit and thus less runtime(?) > > Thanks > Dave > > > - Tim Also another question unrelated to the ones before. I do have a weird bug in my zero sm[1] but I'm unsure where my sm is flawed. Take for example, the probably simplest case: int x = 0;h printf("%d", 42 / x); If I use inform to emit a notice for my state machine result, it seems to be correct and I do get following traversal order (by printing the gimple stmt inside on_stmt): x_2 = 0; _1 = 42 % x_2; # .MEM_4 = VDEF <.MEM_3(D)> printf ("%d", _1); _5 = 0; : # VUSE <.MEM_4> return _5; But if i use my zero_diagnostics and sm_ctxt->warn to emit the warning, I get an unexpected traversal order of: x_2 = 0; _1 = 42 / x_2; # .MEM_4 = VDEF <.MEM_3(D)> printf ("%d", _1); _5 = 0; : # VUSE <.MEM_4> return _5; x_2 = 0; <-- why do I get these stmts again but they are not as duplicated in the e-supergraph? _1 = 42 / x_2; _5 = 0; _1 = 42 / x_2; _5 = 0; I tracked the cause down the call stack to m_saved_diagnostics.safe_push (sd); inside diagnostic_manager::add_diagnostic. For whatever reason, the pushing of diagnostics bricks the zero sm. It might be a embarrassing error on my side, but I'm stuck on this and can't seem to find what I'm doing wrong. - Tim [1] https://github.com/timll/gcc/blob/castsize/gcc/analyzer/sm-zero.cc#L181