Pettis-Hansen code reordering causes boot image compilation to be non-deterministic

Description

[Steve asked me to write this up so it doesn't get forgotten]

Pettis-Hansen code reordering (PLDI 1990) is on by default, and due to its implementation causes boot image compilation to be non-deterministic (that is, running `bin/buildit localhost production` multiple times will generate non-trivially different code). Comparing 10 production builds, all compiled with `bin/buildit localhost production`, showed a performance difference of up to 6% between builds, caused by this non-determinism.

Our implementation of PH iterates over HashMaps at the end of the algorithm to arrange the low-frequency CFG blocks that haven't been allocated. This case is executed fairly often in boot image compilation because there is little branch frequency information to use. The iteration over a HashMap causes the non-determinism.

This is trivially fixed by using LinkedHashMaps instead, which will respect insertion order when iterating. The patch is attached. I verified that multiple builds with this fix generated identical code images, and experimentally the previous variation between builds is gone with this change.

By way of further investigation, we wanted to know the impact PH has in a modern compiler. The attached graph shows the variation caused by turning PH on/off for either the runtime or the boot image. The conclusion is that it has varying effects, slowing some benchmarks significantly (3% for _202_jess), speeding others (1.5% for hsqldb), and having conflicting effects on some (e.g. chart). Overall, it's a wash, with no difference in the average case.

Environment

None

Status

Assignee

DaveG

Reporter

James Bornholt

Labels

None

Components

Fix versions

Affects versions

Priority

Medium
Configure