# HG changeset patch
# User Tom Rodriguez <tom.rodriguez@oracle.com>
# Date 1429036632 25200
# Node ID 5541e9c74d384640fec2a4032c76dd447741cb51
# Parent  820420c8713cf65b926920fe5f3c8dbd9fa58135
LocationMarker worklist should be unique

diff -r 820420c8713c -r 5541e9c74d38 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRInstruction.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRInstruction.java	Tue Apr 14 11:37:06 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRInstruction.java	Tue Apr 14 11:37:12 2015 -0700
@@ -37,8 +37,6 @@
  * The base class for an {@code LIRInstruction}.
  */
 public abstract class LIRInstruction {
-    public static final Value[] NO_OPERANDS = {};
-
     /**
      * Constants denoting how a LIR instruction uses an operand.
      */
diff -r 820420c8713c -r 5541e9c74d38 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	Tue Apr 14 11:37:06 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LocationMarker.java	Tue Apr 14 11:37:12 2015 -0700
@@ -54,10 +54,55 @@
 
     @Override
     protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) {
-        new Marker(lirGenRes.getLIR(), lirGenRes.getFrameMap()).build();
+        new Marker<B>(lirGenRes.getLIR(), lirGenRes.getFrameMap()).build();
     }
 
-    private static final class Marker {
+    /**
+     * Ensures that an element is only in the worklist once.
+     *
+     * @param <T>
+     */
+    static class UniqueWorkList<T extends AbstractBlockBase<T>> extends ArrayDeque<T> {
+        private static final long serialVersionUID = 8009554570990975712L;
+        BitSet valid;
+
+        public UniqueWorkList(int size) {
+            this.valid = new BitSet(size);
+        }
+
+        @Override
+        public T poll() {
+            T result = super.poll();
+            if (result != null) {
+                valid.set(result.getId(), false);
+            }
+            return result;
+        }
+
+        @Override
+        public boolean add(T pred) {
+            if (!valid.get(pred.getId())) {
+                valid.set(pred.getId(), true);
+                return super.add(pred);
+            }
+            return false;
+        }
+
+        @Override
+        public boolean addAll(Collection<? extends T> collection) {
+            boolean changed = false;
+            for (T element : collection) {
+                if (!valid.get(element.getId())) {
+                    valid.set(element.getId(), true);
+                    super.add(element);
+                    changed = true;
+                }
+            }
+            return changed;
+        }
+    }
+
+    private static final class Marker<T extends AbstractBlockBase<T>> {
         private final LIR lir;
         private final FrameMap frameMap;
         private final RegisterAttributes[] registerAttributes;
@@ -72,16 +117,17 @@
             liveOutMap = new BlockMap<>(lir.getControlFlowGraph());
         }
 
-        private void build() {
-            Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>();
+        @SuppressWarnings("unchecked")
+        void build() {
+            UniqueWorkList<T> worklist = new UniqueWorkList<>(lir.getControlFlowGraph().getBlocks().size());
             for (int i = lir.getControlFlowGraph().getBlocks().size() - 1; i >= 0; i--) {
-                worklist.add(lir.getControlFlowGraph().getBlocks().get(i));
+                worklist.add((T) lir.getControlFlowGraph().getBlocks().get(i));
             }
             for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
                 liveInMap.put(block, frameMap.initReferenceMap(true));
             }
             while (!worklist.isEmpty()) {
-                AbstractBlockBase<?> block = worklist.poll();
+                AbstractBlockBase<T> block = worklist.poll();
                 processBlock(block, worklist);
             }
         }
@@ -101,7 +147,7 @@
             return false;
         }
 
-        private void processBlock(AbstractBlockBase<?> block, Deque<AbstractBlockBase<?>> worklist) {
+        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(liveOutMap.get(block).clone());