My favorite trick when cutting down the search space of possible programs is to generate DAGs directly instead of an instruction sequence. This way, it's easier to write rules that avoid nonsensical programs and to some extent avoid generating multiple equivalent programs.
For example to avoid programs that overwrite calculations you make sure that each node in the generated DAG has something that depends on it.
In a suitable environment the DAG can then be executed directly without lowering to a sequence of instructions.