--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/Compiler/src/com/sun/c1x/opt/LivenessMarker.java	Wed Apr 27 11:43:22 2011 +0200
@@ -0,0 +1,199 @@
+/*
+ * Copyright (c) 2009, 2011, 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.sun.c1x.opt;
+
+import static com.sun.c1x.ir.Value.Flag.*;
+
+import com.sun.c1x.*;
+import com.sun.c1x.graph.*;
+import com.sun.c1x.ir.*;
+import com.sun.c1x.value.*;
+
+/**
+ * The {@code LivenessMarker} class walks over an IR graph and marks instructions
+ * whose values are live, either because they are needed to compute the method's result,
+ * may produce a side-effect, or are needed for deoptimization.
+ *
+ * @author Ben L. Titzer
+ */
+public final class LivenessMarker {
+
+    final IR ir;
+
+    final InstructionMarker deoptMarker = new InstructionMarker(LiveDeopt);
+    final InstructionMarker valueMarker = new InstructionMarker(LiveValue);
+
+    int count;
+
+    /**
+     * Creates a new liveness marking instance and marks live instructions.
+     * @param ir the IR to mark
+     */
+    public LivenessMarker(IR ir) {
+        this.ir = ir;
+        markRoots();
+    }
+
+    private void markRoots() {
+        // first pass: mark root instructions and their inputs
+        ir.startBlock.iteratePreOrder(new BlockClosure() {
+            public void apply(BlockBegin block) {
+                block.stateBefore().valuesDo(deoptMarker);
+                if (block.stateAfter() != null) {
+                    block.stateAfter().valuesDo(deoptMarker);
+                }
+                Instruction i = block;
+                while ((i = i.next()) != null) {
+                    // visit all instructions first, marking control dependent and side-effects
+                    markRootInstr(i);
+                }
+            }
+        });
+
+        // propagate liveness flags to inputs of instructions
+        valueMarker.markAll();
+        deoptMarker.markAll();
+    }
+
+    public int liveCount() {
+        return count;
+    }
+
+    public void removeDeadCode() {
+        // second pass: remove dead instructions from blocks
+        ir.startBlock.iteratePreOrder(new BlockClosure() {
+            public void apply(BlockBegin block) {
+                Instruction prev = block;
+                Instruction i = block.next();
+                while (i != null) {
+                    if (i.isLive()) {
+                        prev.resetNext(i); // skip any previous dead instructions
+                        prev = i;
+                    } else {
+                        C1XMetrics.DeadCodeEliminated++;
+                    }
+                    i = i.next();
+                }
+            }
+        });
+        // clear all marks on all instructions
+        valueMarker.clearAll();
+        deoptMarker.clearAll();
+    }
+
+    private static class Link {
+        final Value value;
+        Link next;
+
+        Link(Value v) {
+            this.value = v;
+        }
+    }
+
+    private final class InstructionMarker implements ValueClosure {
+        final Value.Flag reason;
+        Link head;
+        Link tail;
+
+        public InstructionMarker(Value.Flag reason) {
+            this.reason = reason;
+        }
+
+        public Value apply(Value i) {
+            if (!i.checkFlag(reason) && !i.isDeadPhi()) {
+                // set the flag and add to the queue
+                setFlag(i, reason);
+                if (head == null) {
+                    head = tail = new Link(i);
+                } else {
+                    tail.next = new Link(i);
+                    tail = tail.next;
+                }
+            }
+            return i;
+        }
+
+        private void markAll() {
+            Link cursor = head;
+            while (cursor != null) {
+                markInputs(cursor.value);
+                cursor = cursor.next;
+            }
+        }
+
+        private void clearAll() {
+            Link cursor = head;
+            while (cursor != null) {
+                cursor.value.clearLive();
+                cursor = cursor.next;
+            }
+        }
+
+        private void markInputs(Value i) {
+            if (!i.isDeadPhi()) {
+                i.inputValuesDo(this);
+                if (i instanceof Phi) {
+                    // phis are special
+                    Phi phi = (Phi) i;
+                    int max = phi.inputCount();
+                    for (int j = 0; j < max; j++) {
+                        apply(phi.inputAt(j));
+                    }
+                }
+            }
+        }
+    }
+
+    void markRootInstr(Instruction i) {
+        FrameState stateBefore = i.stateBefore();
+        if (stateBefore != null) {
+            // stateBefore != null implies that this instruction may have side effects
+            stateBefore.valuesDo(deoptMarker);
+            i.inputValuesDo(valueMarker);
+            setFlag(i, LiveSideEffect);
+        } else if (i.checkFlag(LiveStore)) {
+            // instruction is a store that cannot be eliminated
+            i.inputValuesDo(valueMarker);
+            setFlag(i, LiveSideEffect);
+        } else if (i.checkFlag(LiveSideEffect)) {
+            // instruction has a side effect
+            i.inputValuesDo(valueMarker);
+        }
+        if (i instanceof BlockEnd) {
+            // input values to block ends are control dependencies
+            i.inputValuesDo(valueMarker);
+            setFlag(i, LiveControl);
+        }
+        FrameState stateAfter = i.stateAfter();
+        if (stateAfter != null) {
+            stateAfter.valuesDo(deoptMarker);
+        }
+    }
+
+    void setFlag(Value i, Value.Flag flag) {
+        if (!i.isLive()) {
+            count++;
+        }
+        i.setFlag(flag);
+    }
+}