Another approach would be to walk the SSA_NAME list and generate a bitmap of all the names which have a signed type or which were defined by a conversion to an unsigned type from a signed type.
At that point what's left is just the PHIs. So we'd walk the dominator tree in RPO order to process the PHIs. You don't have to recurse on the actual PHI arguments, just look at each one and see if it was already marked as being signed or derived from a signed type. If all the args are marked as signed or derived from a signed type, then the PHI can be marked as well.
That may be more costly in the common case, but should avoid the pathological cases Richi is worried about.
jeff
