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?