Just some general advice:

It's probably an optimization or bug fix having bad side-effects.

If I were you I'd try to see if the regex-op-trees stay the same with use re 'debug';

see re for details.

You could also have a look into perldelta 5.20, to see what changed with 5.20.

edit

And you should provide a minimal example reproducing the problem, I suppose your benchmark is only reflecting the "real" program we can't probably know.

update

A guess: The /o modifier is nowadays mostly useless (IIRC)!

Try to measure if it's probably causing the problem.