It is generally considered a bug in a compiler if its output is nondeterministic. Of course, compilers are large, complex beasts, and nondeterminism is so easy to accidentally introduce (e.g., do a "for each" in a map where the key is a pointer), that it's probably not too hard to find cases that have nondeterminism.

> PGO seems like it ought to have a random element.

PGO should be deterministic based on the runs used to generate the profile. The runs are tracking information that should be deterministic--how many times does the the branch get taken versus not taken, etc. HWPGO, which relies on hardware counters to generate profiling information, may be less deterministic because the hardware counters end up having some statistical slip to them.