That would surely be the second option? Treating all permutations the same means changing the object representation to keep ICs monomorphic across orderings.

Unless you forbid any impure operations you can't just deoptimise and re-execute code to then store the ordering. (I'm sure this isn't what you meant, and I'm probably being silly!)