[Bug middle-end/18628] [4.0 regression] miscompilation of switch statement in loop

["roger at eyesopen dot com" <gcc-bugzilla at gcc dot gnu dot org>]

------- Additional Comments From roger at eyesopen dot com  2004-11-28 18:01 -------
Hmm... This is a difficult one.  We manage to split a table jump sequence, and
introduce a label between the indexed load of a jump table and the indirect
jump.  We then hoist the indexed load, and later simplify/GCSE/CSE it to a load
of one of its symbol_ref from the tablejump vector.  Hence we have a load of a
symbol, in a block that then jumps to the indirect jump.  Everything is
consistent at this point, even though the load of symbol_ref doesn't appear in
the CFG until we later decide to forward one of the edges from the tablejump
(but without realizing that a REG_LABEL copy has been made of it, and eventually
the incoming edge count for that block reaches zero, so we delete the block,
leaving a dangling reference.

There are several ways of addressing this issue:
[1] If we ever split a tablejump by inserting a label between its load and the
indirect jump, we need to treat it as a generic indirect jump, potentially
jumping to any (case) label in the function/program.
[2] We could prohibit the splitting of tablejumps as above.  Either by keeping
things together in the middle-end or by changing backends by only splitting the
tablejump after these optimization passes (reload?).
[3] We could prohibit the simplification that extracts a symbol ref out of a
jump table, so that an indexed load is always performed a run-time, and so
changing the jump table is always safe.
[4] Perhaps we could tag the jump table to indicate that once we've extracted a
value out of it, it's effectively constant and we can no longer redirect edges.
[5] At the point that we extract the symbol ref from the jump table, we could
mark the destination symbol as LABEL_PRESERVE_P to indicate that it shouldn't
be deleted.  Unfortunately, it looks like LABEL_PRESERVE_P isn't honored by
the try_cfg_optimize routine that deletes basic blocks, but perhaps we could
refuse to thread jumps over a label marked LABEL_PRESERVE.
[6] It might be sufficent to avoid threading jumps over basic blocks whose
LABEL_NUSES doesn't match their EDGE_CODE(preds).
[7] Perhaps tree-ssa could recognize the potential infinite loop and prevent
the RTL optimizers by getting confused by it (__builtin_infinite_loop()?).

[8] As an enhancement, if we have two consecutive labels the decision of which
to replace could be tweaked to check whether one of the labels is marked
PRESERVED or has excess NUSES.  There's also a performance issue given two
labels at the same location, we should retain the label with the most incoming
edges to minimize the number of jumps/edges that need to be redirected.


Basically, its not if-conversion that's at fault, but a bad interation between
the cfg_optimize function it calls, and the cumulative effects of the earlier
optimizations (gcse for hoisting the load, loop for introducing the empty
loop header, etc...)  All of these transformations legitimately improve
performance on real world code like bytecode interpreters, hence choosing
which one (or combination) to disable looks to be a compromise.

Anyway how best to fix this really requires the attention of a CFG guru,
perhaps either Jan or RTH.  Certainly Zdenek's patch is innocent, this is an
underlying design issue.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18628