# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1422698505 -3600
# Node ID a4c9a0fe4bd587c928a2e14a5d0d8ae01685e34d
# Parent  3ec39188b0eea4a75befb65f5f3b75aa6f16c7e1
LSStackSlotAllocator: use priority queue.

diff -r 3ec39188b0ee -r a4c9a0fe4bd5 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java	Sat Jan 31 10:49:20 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java	Sat Jan 31 11:01:45 2015 +0100
@@ -71,8 +71,8 @@
         private final LIR lir;
         private final FrameMapBuilderTool frameMapBuilder;
         private final StackInterval[] stackSlotMap;
-        private LinkedList<StackInterval> unhandled;
-        private LinkedList<StackInterval> active;
+        private PriorityQueue<StackInterval> unhandled;
+        private PriorityQueue<StackInterval> active;
 
         private List<? extends AbstractBlock<?>> sortedBlocks;
 
@@ -357,19 +357,14 @@
         }
 
         private void createUnhandled() {
-            unhandled = new LinkedList<>();
-            active = new LinkedList<>();
-            forEachInterval(this::insertSortedByFrom);
-        }
+            Comparator<? super StackInterval> insertByFrom = (a, b) -> a.from() - b.from();
+            Comparator<? super StackInterval> insertByTo = (a, b) -> a.to() - b.to();
 
-        private void insertSortedByFrom(StackInterval interval) {
-            unhandled.add(interval);
-            unhandled.sort((a, b) -> a.from() - b.from());
-        }
+            unhandled = new PriorityQueue<>(insertByFrom);
+            active = new PriorityQueue<>(insertByTo);
 
-        private void insertSortedByTo(StackInterval interval) {
-            active.add(interval);
-            active.sort((a, b) -> a.to() - b.to());
+            // add all intervals to unhandled list
+            forEachInterval(unhandled::add);
         }
 
         private void allocateStackSlots() {
@@ -468,17 +463,17 @@
             if (unhandled.isEmpty()) {
                 return null;
             }
-            StackInterval next = unhandled.pollFirst();
+            StackInterval next = unhandled.poll();
             for (int id = next.from(); activePeekId() < id;) {
-                finished(active.pollFirst());
+                finished(active.poll());
             }
             Debug.log("active %s", next);
-            insertSortedByTo(next);
+            active.add(next);
             return next;
         }
 
         private int activePeekId() {
-            StackInterval first = active.peekFirst();
+            StackInterval first = active.peek();
             if (first == null) {
                 return Integer.MAX_VALUE;
             }