Objects in SortTODObjectReferenceStack popped from data structure in wrong order, causing Merlin traces to be incorrect

The Merlin codes in Jikes RVM uses a SortTODObjectReferenceStack to maintain a list of all dead objects during each collection. After the collection, the data structure is sorted from high to low, and ObjectReferences are expected to be popped off in high-to-low order. However, the ObjectReferences are actually popped off in low-to-high order, which causes the Merlin algorithm to compute incorrect death times for objects.

The problem is that the data structure that stores the ObjectReferences is supposed to be a deque, so you should be able to push/pop to either end of it. Somewhere along the line it lost the ability to pop from one end, and the Merlin code assumes you are popping from the other end of the data structure. So the references come out in the wrong order.

I have attached two patches against 2.9.1. The first, gctrace-build-run.diff, allows you first to build and run the GCTrace configuration (it did not work in stock 2.9.1). The second, gctrace-sort-order-fix.diff, fixes the SortTODObjectReferenceStack issue described in this bug report.