Being able to do very basic JITting on the GPU would be a great first step – load/store operations when evaluating the tapes are terrible for memory access, since they use global memory rather than registers.
In another project [1], I found a 2-6x speedup in going from an interpreter to a fully-compiled shader, so this can make a huge difference!