# HG changeset patch
# User Tom Rodriguez <tom.rodriguez@oracle.com>
# Date 1433439983 25200
# Node ID bc2ec35a7189524433420d09ff7523044c8b6353
# Parent  df9d2375512a1a908174918954e4dd401b35222c
Use dense index when possible for location marker

diff -r df9d2375512a -r bc2ec35a7189 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LocationMarker.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LocationMarker.java	Wed Jun 03 20:24:05 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LocationMarker.java	Thu Jun 04 10:46:23 2015 -0700
@@ -25,6 +25,7 @@
 import static com.oracle.jvmci.code.ValueUtil.*;
 
 import java.util.*;
+import java.util.function.*;
 
 import com.oracle.graal.compiler.common.alloc.*;
 import com.oracle.graal.compiler.common.cfg.*;
@@ -104,51 +105,203 @@
         }
     }
 
-    private static final class LiveValueSet implements Iterable<Value> {
-        private static final Object MARKER = new Object();
+    private static final class ValueSet {
+        private Value[] values;
 
-        private final HashMap<Value, Object> map;
-
-        public LiveValueSet() {
-            map = new HashMap<>();
+        ValueSet() {
+            values = Value.NO_VALUES;
         }
 
-        public LiveValueSet(LiveValueSet s) {
-            map = new HashMap<>(s.map);
+        ValueSet(ValueSet other) {
+            int limit = other.values.length;
+            while (limit > 0) {
+                if (other.values[limit - 1] == null) {
+                    limit--;
+                    continue;
+                }
+                break;
+            }
+            values = new Value[limit];
+            System.arraycopy(other.values, 0, values, 0, values.length);
         }
 
-        public void put(Value v) {
-            map.put(v, MARKER);
+        void put(int index, Value value) {
+            if (value != null && value.getLIRKind().isValue()) {
+                return;
+            }
+            if (values.length <= index) {
+                if (value == null) {
+                    return;
+                }
+                Value[] newValues = new Value[index + 1];
+                System.arraycopy(values, 0, newValues, 0, values.length);
+                values = newValues;
+                values[index] = value;
+            } else {
+                values[index] = value;
+            }
         }
 
-        public void putAll(LiveValueSet v) {
-            map.putAll(v.map);
-        }
-
-        public void remove(Value v) {
-            map.remove(v);
-        }
-
-        public Iterator<Value> iterator() {
-            return map.keySet().iterator();
+        public void putAll(ValueSet stack) {
+            Value[] otherValues = stack.values;
+            int limit = otherValues.length;
+            if (limit > values.length) {
+                while (limit > 0) {
+                    if (otherValues[limit - 1] == null) {
+                        limit--;
+                        continue;
+                    }
+                    break;
+                }
+                if (limit > values.length) {
+                    Value[] newValues = new Value[limit];
+                    System.arraycopy(values, 0, newValues, 0, values.length);
+                    values = newValues;
+                }
+            }
+            for (int i = 0; i < limit; i++) {
+                Value value = otherValues[i];
+                if (value != null) {
+                    values[i] = value;
+                }
+            }
         }
 
         @Override
-        public boolean equals(Object obj) {
-            if (obj instanceof LiveValueSet) {
-                return map.equals(((LiveValueSet) obj).map);
-            } else {
-                return false;
+        public boolean equals(Object other) {
+            if (other instanceof ValueSet) {
+                ValueSet that = (ValueSet) other;
+                int limit = Math.min(values.length, that.values.length);
+                for (int i = 0; i < limit; i++) {
+                    if (!Objects.equals(values[i], that.values[i])) {
+                        return false;
+                    }
+                }
+                for (int i = limit; i < values.length; i++) {
+                    if (values[i] != null) {
+                        return false;
+                    }
+                }
+                for (int i = limit; i < that.values.length; i++) {
+                    if (that.values[i] != null) {
+                        return false;
+                    }
+                }
+                return true;
+            }
+            return false;
+        }
+
+        public void addLiveValues(ReferenceMap refMap) {
+            for (Value v : values) {
+                if (v != null) {
+                    refMap.addLiveValue(v);
+                }
             }
         }
 
         @Override
         public int hashCode() {
-            return map.hashCode();
+            throw new UnsupportedOperationException();
         }
     }
 
     private static final class Marker<T extends AbstractBlockBase<T>> {
+
+        private final class LiveValueSet implements Consumer<AbstractBlockBase<T>> {
+
+            public void accept(AbstractBlockBase<T> succ) {
+                putAll(liveInMap.get(succ));
+            }
+
+            private final ValueSet registers;
+            private final ValueSet stack;
+            private Set<Value> extraStack;
+
+            public LiveValueSet() {
+                registers = new ValueSet();
+                stack = new ValueSet();
+            }
+
+            public LiveValueSet(LiveValueSet s) {
+                registers = new ValueSet(s.registers);
+                stack = new ValueSet(s.stack);
+                if (s.extraStack != null) {
+                    extraStack = new HashSet<>(s.extraStack);
+                }
+            }
+
+            public void put(Value v) {
+                if (isRegister(v)) {
+                    int index = asRegister(v).getReferenceMapIndex();
+                    registers.put(index, v);
+                } else if (isStackSlot(v)) {
+                    int index = frameMap.offsetForStackSlot(asStackSlot(v));
+                    assert index >= 0;
+                    if (index % 4 == 0) {
+                        stack.put(index / 4, v);
+                    } else {
+                        if (extraStack == null) {
+                            extraStack = new HashSet<>();
+                        }
+                        extraStack.add(v);
+                    }
+                }
+            }
+
+            public void putAll(LiveValueSet v) {
+                registers.putAll(v.registers);
+                stack.putAll(v.stack);
+                if (v.extraStack != null) {
+                    if (extraStack == null) {
+                        extraStack = new HashSet<>();
+                    }
+                    extraStack.addAll(v.extraStack);
+                }
+            }
+
+            public void remove(Value v) {
+                if (isRegister(v)) {
+                    int index = asRegister(v).getReferenceMapIndex();
+                    registers.put(index, null);
+                } else if (isStackSlot(v)) {
+                    int index = frameMap.offsetForStackSlot(asStackSlot(v));
+                    assert index >= 0;
+                    if (index % 4 == 0) {
+                        stack.put(index / 4, null);
+                    } else {
+                        extraStack.remove(v);
+                    }
+                }
+            }
+
+            @SuppressWarnings("unchecked")
+            @Override
+            public boolean equals(Object obj) {
+                if (obj instanceof Marker.LiveValueSet) {
+                    LiveValueSet other = (LiveValueSet) obj;
+                    return registers.equals(other.registers) && stack.equals(other.stack) && Objects.equals(extraStack, other.extraStack);
+                } else {
+                    return false;
+                }
+            }
+
+            @Override
+            public int hashCode() {
+                throw new UnsupportedOperationException();
+            }
+
+            public void addLiveValues(ReferenceMap refMap) {
+                registers.addLiveValues(refMap);
+                stack.addLiveValues(refMap);
+                if (extraStack != null) {
+                    for (Value v : extraStack) {
+                        refMap.addLiveValue(v);
+                    }
+                }
+            }
+        }
+
         private final LIR lir;
         private final FrameMap frameMap;
         private final RegisterAttributes[] registerAttributes;
@@ -181,9 +334,9 @@
         /**
          * Merge outSet with in-set of successors.
          */
-        private boolean updateOutBlock(AbstractBlockBase<?> block) {
+        private boolean updateOutBlock(AbstractBlockBase<T> block) {
             LiveValueSet union = new LiveValueSet();
-            block.getSuccessors().forEach(succ -> union.putAll(liveInMap.get(succ)));
+            block.getSuccessors().forEach(union);
             LiveValueSet outSet = liveOutMap.get(block);
             // check if changed
             if (outSet == null || !union.equals(outSet)) {
@@ -196,13 +349,14 @@
         private void processBlock(AbstractBlockBase<T> block, UniqueWorkList<T> worklist) {
             if (updateOutBlock(block)) {
                 try (Indent indent = Debug.logAndIndent("handle block %s", block)) {
-                    BlockClosure closure = new BlockClosure(new LiveValueSet(liveOutMap.get(block)));
+                    currentSet = new LiveValueSet(liveOutMap.get(block));
                     List<LIRInstruction> instructions = lir.getLIRforBlock(block);
                     for (int i = instructions.size() - 1; i >= 0; i--) {
                         LIRInstruction inst = instructions.get(i);
-                        closure.processInstructionBottomUp(inst);
+                        processInstructionBottomUp(inst);
                     }
-                    liveInMap.put(block, closure.getCurrentSet());
+                    liveInMap.put(block, currentSet);
+                    currentSet = null;
                     worklist.addAll(block.getPredecessors());
                 }
             }
@@ -211,78 +365,68 @@
         private static final EnumSet<OperandFlag> REGISTER_FLAG_SET = EnumSet.of(OperandFlag.REG);
         private static final LIRKind REFERENCE_KIND = LIRKind.reference(Kind.Object);
 
-        private final class BlockClosure {
-            private final LiveValueSet currentSet;
+        private LiveValueSet currentSet;
 
-            private BlockClosure(LiveValueSet set) {
-                currentSet = set;
-            }
+        /**
+         * Process all values of an instruction bottom-up, i.e. definitions before usages. Values
+         * that start or end at the current operation are not included.
+         */
+        private void processInstructionBottomUp(LIRInstruction op) {
+            try (Indent indent = Debug.logAndIndent("handle op %d, %s", op.id(), op)) {
+                // kills
 
-            private LiveValueSet getCurrentSet() {
-                return currentSet;
-            }
+                op.visitEachTemp(defConsumer);
+                op.visitEachOutput(defConsumer);
+                if (op.destroysCallerSavedRegisters()) {
+                    for (Register reg : frameMap.getRegisterConfig().getCallerSaveRegisters()) {
+                        defConsumer.visitValue(reg.asValue(REFERENCE_KIND), OperandMode.TEMP, REGISTER_FLAG_SET);
+                    }
+                }
 
-            /**
-             * Process all values of an instruction bottom-up, i.e. definitions before usages.
-             * Values that start or end at the current operation are not included.
-             */
-            private void processInstructionBottomUp(LIRInstruction op) {
-                try (Indent indent = Debug.logAndIndent("handle op %d, %s", op.id(), op)) {
-                    // kills
+                // gen - values that are considered alive for this state
+                op.visitEachAlive(useConsumer);
+                op.visitEachState(useConsumer);
+                // mark locations
+                op.forEachState(stateConsumer);
+                // gen
+                op.visitEachInput(useConsumer);
+            }
+        }
 
-                    op.visitEachTemp(defConsumer);
-                    op.visitEachOutput(defConsumer);
-                    if (op.destroysCallerSavedRegisters()) {
-                        for (Register reg : frameMap.getRegisterConfig().getCallerSaveRegisters()) {
-                            defConsumer.visitValue(reg.asValue(REFERENCE_KIND), OperandMode.TEMP, REGISTER_FLAG_SET);
-                        }
-                    }
+        InstructionStateProcedure stateConsumer = new InstructionStateProcedure() {
+            public void doState(LIRInstruction inst, LIRFrameState info) {
+                markLocation(inst, info, currentSet);
+            }
+        };
 
-                    // gen - values that are considered alive for this state
-                    op.visitEachAlive(useConsumer);
-                    op.visitEachState(useConsumer);
-                    // mark locations
-                    op.forEachState(stateConsumer);
-                    // gen
-                    op.visitEachInput(useConsumer);
+        ValueConsumer useConsumer = new ValueConsumer() {
+            public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
+                if (shouldProcessValue(operand)) {
+                    // no need to insert values and derived reference
+                    if (Debug.isLogEnabled()) {
+                        Debug.log("set operand: %s", operand);
+                    }
+                    currentSet.put(operand);
                 }
             }
-
-            InstructionStateProcedure stateConsumer = new InstructionStateProcedure() {
-                public void doState(LIRInstruction inst, LIRFrameState info) {
-                    markLocation(inst, info, getCurrentSet());
-                }
-            };
+        };
 
-            ValueConsumer useConsumer = new ValueConsumer() {
-                public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
-                    if (shouldProcessValue(operand)) {
-                        // no need to insert values and derived reference
-                        if (Debug.isLogEnabled()) {
-                            Debug.log("set operand: %s", operand);
-                        }
-                        currentSet.put(operand);
+        ValueConsumer defConsumer = new ValueConsumer() {
+            public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
+                if (shouldProcessValue(operand)) {
+                    if (Debug.isLogEnabled()) {
+                        Debug.log("clear operand: %s", operand);
                     }
+                    currentSet.remove(operand);
+                } else {
+                    assert isIllegal(operand) || operand.getPlatformKind() != Kind.Illegal || mode == OperandMode.TEMP : String.format("Illegal PlatformKind is only allowed for TEMP mode: %s, %s",
+                                    operand, mode);
                 }
-            };
+            }
+        };
 
-            ValueConsumer defConsumer = new ValueConsumer() {
-                public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
-                    if (shouldProcessValue(operand)) {
-                        if (Debug.isLogEnabled()) {
-                            Debug.log("clear operand: %s", operand);
-                        }
-                        currentSet.remove(operand);
-                    } else {
-                        assert isIllegal(operand) || operand.getPlatformKind() != Kind.Illegal || mode == OperandMode.TEMP : String.format(
-                                        "Illegal PlatformKind is only allowed for TEMP mode: %s, %s", operand, mode);
-                    }
-                }
-            };
-
-            protected boolean shouldProcessValue(Value operand) {
-                return (isRegister(operand) && attributes(asRegister(operand)).isAllocatable() || isStackSlot(operand)) && operand.getPlatformKind() != Kind.Illegal;
-            }
+        protected boolean shouldProcessValue(Value operand) {
+            return (isRegister(operand) && attributes(asRegister(operand)).isAllocatable() || isStackSlot(operand)) && operand.getPlatformKind() != Kind.Illegal;
         }
 
         /**
@@ -296,9 +440,7 @@
             ReferenceMap refMap = info.debugInfo().getReferenceMap();
             refMap.reset();
             frameMap.addLiveValues(refMap);
-            for (Value v : values) {
-                refMap.addLiveValue(v);
-            }
+            values.addLiveValues(refMap);
             refMap.finish();
         }