The merge optimization when applied with the destroy handler can be very slow.
I have one case that got speed up from 190s to 12s by this PR:

Original:
SeqOptimizer  OPT_FAST_RUN  time 190.461s for 2161/548 nodes before/after optimization
   1.280s for fgraph.validate()
   132.634s for callback
   time      - (name, class, index) - validate time
   170.167204s - ('merge3', 'MergeOptimizer', 38) - 0.000s
     MergeOptimizer
       nb fail= 7728 merged=    0 constant=    0
       time replace=170.17 validate=0.00 callback=128.92
       callbacks_time
(<theano.gof.toolbox.PreserveNames object at 0x7f46b8864310>, 0.04287838935852051)
(<theano.gof.toolbox.ReplaceValidate object at 0x7f46b33f43d0>, 0.06792092323303223)
(<theano.tensor.opt.ShapeFeature object at 0x7f46b8864890>, 0.44670534133911133)
(<theano.gof.destroyhandler.DestroyHandler object at 0x7f46b4a44810>, 1.9552459716796875)
(<theano.gof.opt.MergeFeature object at 0x7f46b8864650>, 126.08237051963806)
   10.041219s - ('canonicalize', 'EquilibriumOptimizer', 4) - 0.051s

New one:

 SeqOptimizer  OPT_FAST_RUN  time 12.338s for 2161/548 nodes before/after optimization
   1.219s for fgraph.validate()
   3.536s for callback
   time      - (name, class, index) - validate time
   4.779337s - ('gpu_opt', 'SeqOptimizer', 12) - 0.012s
     SeqOptimizer      gpu_opt  time 4.779s for 633/504 nodes before/after optimization
       0.012s for fgraph.validate()
       0.817s for callback
       4.748835s - ('gpu_local_optimizations', 'EquilibriumOptimizer', 1) - 0.012s
...
   0.002217s - ('merge3', 'MergeOptimizer', 38) - 0.000s
     MergeOptimizer
       nb fail=    0 merged=    0 constant=    0
       time replace=0.00 validate=0.00 callback=0.00