[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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?