public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "spop at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation Date: Mon, 16 Mar 2015 21:35:00 -0000 [thread overview] Message-ID: <bug-65177-4-su0ZcEYAZN@http.gcc.gnu.org/bugzilla/> (raw) In-Reply-To: <bug-65177-4@http.gcc.gnu.org/bugzilla/> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65177 Sebastian Pop <spop at gcc dot gnu.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|UNCONFIRMED |ASSIGNED Last reconfirmed| |2015-03-16 Ever confirmed|0 |1 --- Comment #18 from Sebastian Pop <spop at gcc dot gnu.org> --- Before all FSM jump threads the representation looks correct: we would not jump thread from sprv_137 that is a value read from memory: # sprv_49 = PHI <8(4), sprv_14(78)> # sprv_14 = PHI <sprv_5(58), sprv_43(76)> # sprv_5 = PHI <sprv_137(14), sprv_284(49), -1(42)> sprv_137 = state[_136]; After update_ssa in the dom1 pass, the representation looks bogus: # sprv_49 = PHI <8(4), sprv_737(95)> # sprv_737 = PHI <sprv_735(66), sprv_735(67), sprv_736(68), sprv_739(92), 10(88)> # sprv_736 = PHI <sprv_768(67), sprv_738(90)> # sprv_768 = PHI <sprv_764(55), 5(26), sprv_765(58), sprv_766(60), 8(61)> # sprv_764 = PHI <1(13), 7(52)> This representation is incorrect because we would jump thread the value "1" coming from bb 13 into the "switch (sprv_49)". After installing the patch to update the SSA after each FSM jump thread, the representation gets corrupted on generating code for this FSM path: (43, 76) (76, 60) (60, 69) (69, 70) (70, 71) (71, 72) (72, 73) (73, 78) (78, 5) (5, 6) Before we jump thread: ;; basic block 58, loop depth 1, count 0, freq 0 ;; Invalid sum of incoming frequencies 1580, should be 0 ;; prev block 57, next block 59, flags: (NEW, REACHABLE) ;; pred: 14 [100.0%] (FALLTHRU,EXECUTABLE) ;; 49 [9.0%] (FALSE_VALUE,EXECUTABLE) # i_1 = PHI <i_126(14), i_250(49)> # sprv_5 = PHI <sprv_137(14), sprv_284(49)> # .MEM_7 = PHI <.MEM_331(14), .MEM_337(49)> # k_339 = PHI <k_84(14), k_285(49)> if (sprv_5 == -1) goto <bb 59>; else goto <bb 60>; ;; succ: 59 [12.0%] (TRUE_VALUE,EXECUTABLE) ;; 60 [88.0%] (FALSE_VALUE,EXECUTABLE) After update_ssa, we now have two phi nodes sprv_5 and a new phi sprv_450 that will in turn be folded into "1": ;; basic block 58, loop depth 1, count 0, freq 0 ;; Invalid sum of incoming frequencies 1580, should be 0 ;; prev block 57, next block 59, flags: (NEW, REACHABLE) ;; pred: 14 [100.0%] (FALLTHRU,EXECUTABLE) ;; 49 [9.0%] (FALSE_VALUE,EXECUTABLE) # i_1 = PHI <i_126(14), i_250(49)> # sprv_5 = PHI <sprv_137(14), sprv_284(49)> # .MEM_7 = PHI <.MEM_331(14), .MEM_337(49)> # k_339 = PHI <k_84(14), k_285(49)> # sprv_450 = PHI <sprv_449(14), sprv_49(49)> if (sprv_5 == -1) goto <bb 59>; else goto <bb 60>; ;; succ: 59 [12.0%] (TRUE_VALUE,EXECUTABLE) ;; 60 [88.0%] (FALSE_VALUE,EXECUTABLE) On the jump thread (43, 76) (76, 60) (60, 69) (69, 70) (70, 71) (71, 72) (72, 73) (73, 78) (78, 5) (5, 6) there is a diamond on the jump threaded path: (70, 71) (71, 72) (72, 73) and (70, 73). When using copy_bbs we first copy all the bbs in the path, and then update all the edges: if (!(e->dest->flags & BB_DUPLICATED)) continue; redirect_edge_and_branch_force (e, get_bb_copy (e->dest)); And so this will redirect the edges of the copied region to the copied blocks, creating a diamond in the copied region. This invalidates the single entry property we want for an SEME region. We need to keep the exits from the jump thread path as they are, going to the original code, and not to the copied blocks: these exits are exceptions that do not carry the same state which guarantes the property we are propagating. In a jump thread path all nodes have to be walked through in order for the propagated property to be still holding. In this case we have a diamond that may shortcut the execution of some basic blocks on the jump thread path, and instead of taking the exception edge outside the jump thread, it lands back again on the copied region invalidating the assumption we were propagating from the beginning of the jump thread. We want the jump thread code generator to create a SEME region: that is a Single Entry Multiple Exits region. In the case of a diamond, with the current version of copy_bbs we would end up with a diamond on the copied region, and that invalidates the single entry of the SEME. Jeff, there are two ways to fix this: - one way is to discard jump threads with diamonds, - or we can fix seme_copier to only redirect edges that are on the jump thread path. Which one do you like most?
next prev parent reply other threads:[~2015-03-16 21:35 UTC|newest] Thread overview: 27+ messages / expand[flat|nested] mbox.gz Atom feed top 2015-02-23 15:49 [Bug tree-optimization/65177] New: " marxin at gcc dot gnu.org 2015-02-23 15:58 ` [Bug tree-optimization/65177] " rguenth at gcc dot gnu.org 2015-02-23 16:19 ` trippels at gcc dot gnu.org 2015-02-23 17:41 ` marxin at gcc dot gnu.org 2015-02-23 17:48 ` spop at gcc dot gnu.org 2015-02-23 17:49 ` spop at gcc dot gnu.org 2015-02-25 21:33 ` mpolacek at gcc dot gnu.org 2015-02-25 23:05 ` spop at gcc dot gnu.org 2015-03-09 14:26 ` jakub at gcc dot gnu.org 2015-03-10 22:08 ` law at redhat dot com 2015-03-10 22:39 ` spop at gcc dot gnu.org 2015-03-10 22:42 ` spop at gcc dot gnu.org 2015-03-10 22:49 ` law at redhat dot com 2015-03-10 22:57 ` spop at gcc dot gnu.org 2015-03-10 23:03 ` law at redhat dot com 2015-03-11 16:27 ` spop at gcc dot gnu.org 2015-03-11 21:45 ` law at redhat dot com 2015-03-13 20:47 ` spop at gcc dot gnu.org 2015-03-13 21:05 ` spop at gcc dot gnu.org 2015-03-16 21:35 ` spop at gcc dot gnu.org [this message] 2015-03-17 19:05 ` law at redhat dot com 2015-03-17 20:15 ` spop at gcc dot gnu.org 2015-03-24 13:47 ` law at redhat dot com 2015-03-24 16:49 ` spop at gcc dot gnu.org 2015-03-25 23:26 ` spop at gcc dot gnu.org 2015-03-25 23:43 ` spop at gcc dot gnu.org 2015-10-28 9:01 ` yroux at gcc dot gnu.org
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-65177-4-su0ZcEYAZN@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).