[imtringued]

You don't need expensive combinatorial logic. You just use a predictor to decide where the instruction boundaries are. This is the same strategy CPUs have used for branch predictors. Now your performance merely depends on the accuracy of the branch predictors and the prevalence of difficult to predict instruction sequences. That is hardly a show stopper for the high end and you have to remember that compilers try to optimize their code, so there is no reason for them to produce slow code on purpose.