slavapestov/factor — pull request #1196 by bjourne (2014-11-11 12:42:44+00:00)
Title: Schedule instructions randomness

This pr is supposed to fix #1187. It got bigger than intended because I found the vocabs with the bugs opaque and hard to understand so I had to simplify them first. But I also wrote a lot of unit tests so I dont think I broke anything, but who knows. :)

The first problem with that the ordering was unstable was `keys first`. A hash's keys have no predictable order. So now there is `tiebreak-parents` which guarantees a stable order.

The second problem, `##peek` comes after `##allot` but before the last `##set-slot-imm` initialization, is annoying. I think the algorithm in the paper mentioned in scheduling.factor assumes the instructions are side-effect free. `##peek` can cause a stack underflow so it isn't. Only way I can think of to fix that is to add peek to `initial-insn` which prevents the optimization pass from moving most ##peeks. I think that fixes this bug, the big downside is that it makes the optimization pass less powerful.

On x64 you get 7600 ##spill instructions in the image vs 7300 previously which is mostly irrelevant. On x86, 28000 instead of 24000, which is a big difference but probably doesn't affect performance so much anyway.