Suppose a block B has n predecessors, where n >= 1. Call the predecessors pred_1, ..., pred_n.

Suppose there are ids, id_1, ... id_n (not necessarily distinct), such that:

• For each i, id_i is available at the end of pred_i
• The id_i's are all synonymous and all have the same type

Then we can add a new instruction to the start of B, of the form:

%fresh_id = OpPhi %type %pred_1 %id_1 %pred_2 %id_2 ... %pred_n %id_n

and we can add the fact that %fresh_id is synonymous with each id_i (this can be achieved by recording that it is synonymous with one of them, as it will join their equivalence class).

I think this deserves its own transformation class and fuzzer pass, e.g. TransformationAddOpPhiSynonym and FuzzerPassAddOpPhiSynonyms.