# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1423054277 -3600
# Node ID a5f47cb74b1b8fc2f6117a6f002f506d06f5ab78
# Parent  0f3c0639dc3f9679360ad3844600944507cfbb1b# Parent  036c0b9bd4f5d36a18550327505befc35cef89c2
Merge.

diff -r 036c0b9bd4f5 -r a5f47cb74b1b graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderImpl.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderImpl.java	Wed Feb 04 03:22:41 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderImpl.java	Wed Feb 04 13:51:17 2015 +0100
@@ -22,13 +22,19 @@
  */
 package com.oracle.graal.lir.framemap;
 
+import static com.oracle.graal.api.code.ValueUtil.*;
+
 import java.util.*;
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.*;
+import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.debug.Debug.Scope;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.LIRInstruction.OperandFlag;
+import com.oracle.graal.lir.LIRInstruction.OperandMode;
 import com.oracle.graal.lir.gen.*;
 import com.oracle.graal.lir.stackslotalloc.*;
 
@@ -95,6 +101,9 @@
     public FrameMap buildFrameMap(LIRGenerationResult res, StackSlotAllocator allocator) {
         try (Scope s = Debug.scope("StackSlotAllocation")) {
             allocator.allocateStackSlots(this, res);
+            if (Debug.isEnabled()) {
+                verifyStackSlotAllocation(res);
+            }
         }
         for (CallingConvention cc : calls) {
             frameMap.callsMethod(cc);
@@ -103,6 +112,23 @@
         return frameMap;
     }
 
+    private static void verifyStackSlotAllocation(LIRGenerationResult res) {
+        LIR lir = res.getLIR();
+        InstructionValueConsumer verifySlots = (LIRInstruction op, Value value, OperandMode mode, EnumSet<OperandFlag> flags) -> {
+            assert !isVirtualStackSlot(value) : String.format("Instruction %s contains a virtual stack slot %s", op, value);
+        };
+        for (AbstractBlock<?> block : lir.getControlFlowGraph().getBlocks()) {
+            lir.getLIRforBlock(block).forEach(op -> {
+                op.visitEachInput(verifySlots);
+                op.visitEachAlive(verifySlots);
+                op.visitEachState(verifySlots);
+
+                op.visitEachTemp(verifySlots);
+                op.visitEachOutput(verifySlots);
+            });
+        }
+    }
+
     public List<VirtualStackSlot> getStackSlots() {
         return stackSlots;
     }
diff -r 036c0b9bd4f5 -r a5f47cb74b1b graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/FixPointIntervalBuilder.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/FixPointIntervalBuilder.java	Wed Feb 04 03:22:41 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/FixPointIntervalBuilder.java	Wed Feb 04 13:51:17 2015 +0100
@@ -43,6 +43,7 @@
     private final LIR lir;
     private final int maxOpId;
     private final StackInterval[] stackSlotMap;
+    private final HashSet<Integer> usePos;
 
     /**
      * The number of allocated stack slots.
@@ -55,9 +56,15 @@
         this.maxOpId = maxOpId;
         liveInMap = new BlockMap<>(lir.getControlFlowGraph());
         liveOutMap = new BlockMap<>(lir.getControlFlowGraph());
+        this.usePos = new HashSet<>();
     }
 
-    void build() {
+    /**
+     * Builds the lifetime intervals for {@link VirtualStackSlot virtual stack slots}, sets up
+     * {@link #stackSlotMap} and returns a set of use positions, i.e. ids for instructions that
+     * contain virtual stack slots.
+     */
+    Set<Integer> build() {
         Deque<AbstractBlock<?>> worklist = new ArrayDeque<>();
         for (int i = lir.getControlFlowGraph().getBlocks().size() - 1; i >= 0; i--) {
             worklist.add(lir.getControlFlowGraph().getBlocks().get(i));
@@ -69,6 +76,7 @@
             AbstractBlock<?> block = worklist.poll();
             processBlock(block, worklist);
         }
+        return usePos;
     }
 
     /**
@@ -188,6 +196,7 @@
             if (isVirtualStackSlot(operand)) {
                 VirtualStackSlot vslot = asVirtualStackSlot(operand);
                 addUse(vslot, inst, flags);
+                usePos.add(inst.id());
                 Debug.log("set operand: %s", operand);
                 currentSet.set(vslot.getId());
             }
@@ -206,6 +215,7 @@
             if (isVirtualStackSlot(operand)) {
                 VirtualStackSlot vslot = asVirtualStackSlot(operand);
                 addDef(vslot, inst);
+                usePos.add(inst.id());
                 Debug.log("clear operand: %s", operand);
                 currentSet.clear(vslot.getId());
             }
diff -r 036c0b9bd4f5 -r a5f47cb74b1b graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/InstructionNumberer.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/InstructionNumberer.java	Wed Feb 04 13:51:17 2015 +0100
@@ -0,0 +1,104 @@
+/*
+ * 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 static com.oracle.graal.api.code.CodeUtil.*;
+
+import java.util.*;
+
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.lir.*;
+
+public class InstructionNumberer {
+
+    private final LIRInstruction[] opIdToInstructionMap;
+
+    protected InstructionNumberer(LIR lir) {
+        // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node.
+        int numInstructions = 0;
+        for (AbstractBlock<?> block : lir.getControlFlowGraph().getBlocks()) {
+            numInstructions += lir.getLIRforBlock(block).size();
+        }
+
+        // initialize with correct length
+        opIdToInstructionMap = new LIRInstruction[numInstructions];
+    }
+
+    /**
+     * Converts an {@linkplain LIRInstruction#id instruction id} to an instruction index. All LIR
+     * instructions in a method have an index one greater than their linear-scan order predecessor
+     * with the first instruction having an index of 0.
+     */
+    private static int opIdToIndex(int opId) {
+        return opId >> 1;
+    }
+
+    /**
+     * Retrieves the {@link LIRInstruction} based on its {@linkplain LIRInstruction#id id}.
+     *
+     * @param opId an instruction {@linkplain LIRInstruction#id id}
+     * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id}
+     */
+    protected LIRInstruction instructionForId(int opId) {
+        assert isEven(opId) : "opId not even";
+        LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)];
+        assert instr.id() == opId;
+        return instr;
+    }
+
+    /**
+     * Numbers all instructions in all blocks.
+     */
+    protected void numberInstructions(LIR lir, List<? extends AbstractBlock<?>> sortedBlocks) {
+
+        int opId = 0;
+        int index = 0;
+        for (AbstractBlock<?> block : sortedBlocks) {
+
+            List<LIRInstruction> instructions = lir.getLIRforBlock(block);
+
+            int numInst = instructions.size();
+            for (int j = 0; j < numInst; j++) {
+                LIRInstruction op = instructions.get(j);
+                op.setId(opId);
+
+                opIdToInstructionMap[index] = op;
+                assert instructionForId(opId) == op : "must match";
+
+                index++;
+                opId += 2; // numbering of lirOps by two
+            }
+        }
+        assert index == opIdToInstructionMap.length : "must match";
+        assert (index << 1) == opId : "must match: " + (index << 1);
+        assert opId - 2 == maxOpId() : "must match";
+    }
+
+    /**
+     * Gets the highest instruction id allocated by this object.
+     */
+    public int maxOpId() {
+        assert opIdToInstructionMap.length > 0 : "no operations";
+        return (opIdToInstructionMap.length - 1) << 1;
+    }
+}
diff -r 036c0b9bd4f5 -r a5f47cb74b1b 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	Wed Feb 04 03:22:41 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java	Wed Feb 04 13:51:17 2015 +0100
@@ -32,6 +32,7 @@
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.debug.Debug.Scope;
+import com.oracle.graal.debug.internal.*;
 import com.oracle.graal.lir.*;
 import com.oracle.graal.lir.LIRInstruction.OperandFlag;
 import com.oracle.graal.lir.LIRInstruction.OperandMode;
@@ -58,20 +59,29 @@
         // @formatter:on
     }
 
+    private static final DebugTimer MainTimer = Debug.timer("LSStackSlotAllocator");
+    private static final DebugTimer NumInstTimer = Debug.timer("LSStackSlotAllocator[NumberInstruction]");
+    private static final DebugTimer BuildIntervalsTimer = Debug.timer("LSStackSlotAllocator[BuildIntervals]");
+    private static final DebugTimer VerifyIntervalsTimer = Debug.timer("LSStackSlotAllocator[VerifyIntervals]");
+    private static final DebugTimer AllocateSlotsTimer = Debug.timer("LSStackSlotAllocator[AllocateSlots]");
+    private static final DebugTimer AssignSlotsTimer = Debug.timer("LSStackSlotAllocator[AssignSlots]");
+
     public void allocateStackSlots(FrameMapBuilderTool builder, LIRGenerationResult res) {
-        new Allocator(res.getLIR(), builder).allocate();
+        try (TimerCloseable t = MainTimer.start()) {
+            new Allocator(res.getLIR(), builder).allocate();
+        }
     }
 
-    private static final class Allocator {
+    private static final class Allocator extends InstructionNumberer {
         private final LIR lir;
         private final FrameMapBuilderTool frameMapBuilder;
         private final StackInterval[] stackSlotMap;
         private final PriorityQueue<StackInterval> unhandled;
         private final PriorityQueue<StackInterval> active;
         private final List<? extends AbstractBlock<?>> sortedBlocks;
-        private final int maxOpId;
 
         private Allocator(LIR lir, FrameMapBuilderTool frameMapBuilder) {
+            super(lir);
             this.lir = lir;
             this.frameMapBuilder = frameMapBuilder;
             this.stackSlotMap = new StackInterval[frameMapBuilder.getNumberOfStackSlots()];
@@ -82,33 +92,42 @@
             // insert by to
             this.active = new PriorityQueue<>((a, b) -> a.to() - b.to());
 
-            // step 1: number instructions
-            this.maxOpId = numberInstructions(lir, sortedBlocks);
+            try (TimerCloseable t = NumInstTimer.start()) {
+                // step 1: number instructions
+                numberInstructions(lir, sortedBlocks);
+            }
         }
 
         private void allocate() {
             Debug.dump(lir, "After StackSlot numbering");
 
             long currentFrameSize = Debug.isMeterEnabled() ? frameMapBuilder.getFrameMap().currentFrameSize() : 0;
+            Set<Integer> usePos;
             // step 2: build intervals
-            try (Scope s = Debug.scope("StackSlotAllocationBuildIntervals"); Indent indent = Debug.logAndIndent("BuildIntervals")) {
-                buildIntervals();
+            try (Scope s = Debug.scope("StackSlotAllocationBuildIntervals"); Indent indent = Debug.logAndIndent("BuildIntervals"); TimerCloseable t = BuildIntervalsTimer.start()) {
+                usePos = buildIntervals();
             }
             // step 3: verify intervals
             if (Debug.isEnabled()) {
-                verifyIntervals();
+                try (TimerCloseable t = VerifyIntervalsTimer.start()) {
+                    verifyIntervals();
+                }
             }
             if (Debug.isDumpEnabled()) {
                 dumpIntervals("Before stack slot allocation");
             }
             // step 4: allocate stack slots
-            allocateStackSlots();
+            try (TimerCloseable t = AllocateSlotsTimer.start()) {
+                allocateStackSlots();
+            }
             if (Debug.isDumpEnabled()) {
                 dumpIntervals("After stack slot allocation");
             }
 
             // step 5: assign stack slots
-            assignStackSlots();
+            try (TimerCloseable t = AssignSlotsTimer.start()) {
+                assignStackSlots(usePos);
+            }
             Debug.dump(lir, "After StackSlot assignment");
             if (Debug.isMeterEnabled()) {
                 StackSlotAllocator.allocatedFramesize.add(frameMapBuilder.getFrameMap().currentFrameSize() - currentFrameSize);
@@ -116,40 +135,11 @@
         }
 
         // ====================
-        // step 1: number instructions
-        // ====================
-
-        /**
-         * Numbers all instructions in all blocks.
-         *
-         * @return The id of the last operation.
-         */
-        private static int numberInstructions(LIR lir, List<? extends AbstractBlock<?>> sortedBlocks) {
-            int opId = 0;
-            int index = 0;
-            for (AbstractBlock<?> block : sortedBlocks) {
-
-                List<LIRInstruction> instructions = lir.getLIRforBlock(block);
-
-                int numInst = instructions.size();
-                for (int j = 0; j < numInst; j++) {
-                    LIRInstruction op = instructions.get(j);
-                    op.setId(opId);
-
-                    index++;
-                    opId += 2; // numbering of lirOps by two
-                }
-            }
-            assert (index << 1) == opId : "must match: " + (index << 1);
-            return opId - 2;
-        }
-
-        // ====================
         // step 2: build intervals
         // ====================
 
-        private void buildIntervals() {
-            new FixPointIntervalBuilder(lir, stackSlotMap, maxOpId()).build();
+        private Set<Integer> buildIntervals() {
+            return new FixPointIntervalBuilder(lir, stackSlotMap, maxOpId()).build();
         }
 
         // ====================
@@ -335,16 +325,15 @@
         // step 5: assign stack slots
         // ====================
 
-        private void assignStackSlots() {
-            for (AbstractBlock<?> block : sortedBlocks) {
-                lir.getLIRforBlock(block).forEach(op -> {
-                    op.forEachInput(this::assignSlot);
-                    op.forEachAlive(this::assignSlot);
-                    op.forEachState(this::assignSlot);
+        private void assignStackSlots(Set<Integer> usePos) {
+            for (int opId : usePos) {
+                LIRInstruction op = instructionForId(opId);
+                op.forEachInput(this::assignSlot);
+                op.forEachAlive(this::assignSlot);
+                op.forEachState(this::assignSlot);
 
-                    op.forEachTemp(this::assignSlot);
-                    op.forEachOutput(this::assignSlot);
-                });
+                op.forEachTemp(this::assignSlot);
+                op.forEachOutput(this::assignSlot);
             }
         }
 
@@ -368,13 +357,6 @@
         //
         // ====================
 
-        /**
-         * Gets the highest instruction id.
-         */
-        private int maxOpId() {
-            return maxOpId;
-        }
-
         private StackInterval get(VirtualStackSlot stackSlot) {
             return stackSlotMap[stackSlot.getId()];
         }