# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1422696950 -3600
# Node ID e22286559a8b002661fd19fa4cdcf83042aeae40
# Parent  613a2b7f88c31d4a17130ffab454b4bdc787a6ce
StackInterval: replace StackUsePosList with SortedMap.

diff -r 613a2b7f88c3 -r e22286559a8b graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackInterval.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackInterval.java	Sat Jan 31 11:01:26 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackInterval.java	Sat Jan 31 10:35:50 2015 +0100
@@ -22,6 +22,8 @@
  */
 package com.oracle.graal.lir.stackslotalloc;
 
+import java.util.*;
+
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.debug.*;
@@ -34,7 +36,7 @@
     private final LIRKind kind;
     private int from = INVALID_START;
     private int to = INVALID_END;
-    private final StackUsePosList usePos;
+    private final SortedMap<Integer, UseType> usePos;
     private StackSlot location;
 
     public enum UseType {
@@ -46,11 +48,10 @@
     public StackInterval(VirtualStackSlot operand, LIRKind kind) {
         this.operand = operand;
         this.kind = kind;
-        this.usePos = new StackUsePosList();
+        this.usePos = new TreeMap<>();
     }
 
     public boolean verify(LSStackSlotAllocator.Allocator allocator) {
-        assert usePosList().verify();
         // maxOpId + 1 it the last position in the last block (i.e. the "write position")
         assert from >= 0 && to <= allocator.maxOpId() + 1 : String.format("from %d, to %d, maxOpId %d", from, to, allocator.maxOpId());
         return true;
@@ -63,13 +64,15 @@
     public void addUse(int opId) {
         addTo(opId);
         Debug.log("Adding use pos: %d", opId);
-        usePos.add(opId, UseType.M_USE);
+        // we might overwrite the previous entry
+        usePos.put(opId, UseType.M_USE);
     }
 
     public void addDef(int opId) {
         addFrom(opId);
         Debug.log("Adding def pos: %d", opId);
-        usePos.add(opId, UseType.S_DEF);
+        // we might overwrite the previous entry
+        usePos.put(opId, UseType.S_DEF);
     }
 
     public void addTo(int opId) {
@@ -108,7 +111,7 @@
         return to;
     }
 
-    public StackUsePosList usePosList() {
+    public SortedMap<Integer, UseType> usePosList() {
         return usePos;
     }
 
diff -r 613a2b7f88c3 -r e22286559a8b graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackUsePosList.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackUsePosList.java	Sat Jan 31 11:01:26 2015 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,101 +0,0 @@
-/*
- * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-package com.oracle.graal.lir.stackslotalloc;
-
-import java.util.*;
-
-import com.oracle.graal.compiler.common.*;
-import com.oracle.graal.lir.stackslotalloc.StackInterval.*;
-
-public final class StackUsePosList {
-
-    private final LinkedList<Integer> usePosList;
-    private final LinkedList<UseType> typeList;
-
-    StackUsePosList() {
-        this.usePosList = new LinkedList<>();
-        this.typeList = new LinkedList<>();
-    }
-
-    public int size() {
-        return usePosList.size();
-    }
-
-    public int usePos(int i) {
-        return usePosList.get(i);
-    }
-
-    public void add(int opId, UseType type) {
-        if (usePosList.isEmpty() || opId <= usePosList.getLast()) {
-            usePosList.add(opId);
-            typeList.add(type);
-        } else if (opId >= usePosList.getFirst()) {
-            usePosList.addFirst(opId);
-            typeList.addFirst(type);
-        } else {
-            int size = usePosList.size();
-
-            assert size >= 2 : "Should be handled by the cases above";
-            assert size == typeList.size() : "types and use pos out of sync";
-
-            ListIterator<Integer> posIt = usePosList.listIterator(size - 1);
-            ListIterator<UseType> typeIt = typeList.listIterator(size - 1);
-
-            // we start with size-2 because we know it will not inserted at the end
-            while (posIt.hasPrevious()) {
-                assert posIt.nextIndex() == typeIt.nextIndex();
-                int current = posIt.previous();
-
-                if (current >= opId) {
-                    posIt.next();
-                    posIt.add(opId);
-                    typeIt.add(type);
-                    assert verify();
-                    return;
-                }
-                typeIt.previous();
-            }
-            GraalInternalError.shouldNotReachHere(String.format("Unable to insert %d into %s", opId, usePosList));
-        }
-    }
-
-    public UseType getType(int i) {
-        return typeList.get(i);
-    }
-
-    @Override
-    public String toString() {
-        return usePosList.toString() + System.lineSeparator() + typeList.toString();
-    }
-
-    public boolean verify() {
-        int prev = -1;
-        for (int i = usePosList.size() - 1; i >= 0; --i) {
-            int current = usePosList.get(i);
-            assert prev <= current : String.format("use positions not sorted: %d after %d", current, prev);
-            prev = current;
-        }
-        return true;
-    }
-
-}
diff -r 613a2b7f88c3 -r e22286559a8b graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Sat Jan 31 11:01:26 2015 +0100
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Sat Jan 31 10:35:50 2015 +0100
@@ -26,6 +26,7 @@
 
 import java.io.*;
 import java.util.*;
+import java.util.Map.Entry;
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
@@ -38,6 +39,7 @@
 import com.oracle.graal.java.BciBlockMapping.BciBlock;
 import com.oracle.graal.lir.*;
 import com.oracle.graal.lir.stackslotalloc.*;
+import com.oracle.graal.lir.stackslotalloc.StackInterval.UseType;
 import com.oracle.graal.nodeinfo.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
@@ -588,11 +590,12 @@
 
         // print use positions
         int prev = -1;
-        StackUsePosList usePosList = interval.usePosList();
-        for (int i = usePosList.size() - 1; i >= 0; --i) {
-            assert prev <= usePosList.usePos(i) : "use positions not sorted";
-            out.printf("%d %s ", usePosList.usePos(i), usePosList.getType(i));
-            prev = usePosList.usePos(i);
+        for (Entry<Integer, UseType> e : interval.usePosList().entrySet()) {
+            int usePos = e.getKey();
+            UseType useType = e.getValue();
+            assert prev <= usePos : "use positions not sorted";
+            out.printf("%d %s ", usePos, useType);
+            prev = usePos;
         }
 
         // print spill state