--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/GraalCompiler/src/com/sun/c1x/opt/BlockMerger.java	Wed Apr 27 11:50:44 2011 +0200
@@ -0,0 +1,132 @@
+/*
+ * Copyright (c) 2009, 2010, 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 com.sun.c1x.*;
+import com.sun.c1x.graph.*;
+import com.sun.c1x.ir.*;
+import com.sun.c1x.value.*;
+import com.sun.c1x.value.FrameState.*;
+
+/**
+ * This class implements block merging, which combines adjacent basic blocks into a larger
+ * basic block, and block skipping, which removes empty blocks that end in a Goto with
+ * their target.
+ *
+ * @author Ben L. Titzer
+ */
+public class BlockMerger implements BlockClosure {
+
+    private final BlockBegin startBlock;
+    private final IR ir;
+
+    public BlockMerger(IR ir) {
+        this.ir = ir;
+        startBlock = ir.startBlock;
+        startBlock.iteratePreOrder(this);
+    }
+
+    public void apply(BlockBegin block) {
+        while (block.end() instanceof Goto && block != startBlock) {
+            BlockEnd end = block.end();
+            BlockBegin sux = end.defaultSuccessor();
+
+            assert end.successors().size() == 1 : "end must have exactly one successor";
+            assert !sux.isExceptionEntry() : "should not have Goto to exception entry";
+
+            if (!end.isSafepoint()) {
+                if (sux.numberOfPreds() == 1) {
+                    // the successor has only one predecessor, merge it into this block
+                    mergeBlocks(block, sux, end);
+                    C1XMetrics.BlocksMerged++;
+                    continue;
+                } else if (C1XOptions.OptBlockSkipping && block.next() == end && !block.isExceptionEntry()) {
+                    // the successor has multiple predecessors, but this block is empty
+                    skipBlock(block, sux, end);
+                    break;
+                }
+            }
+            break;
+        }
+    }
+
+    private void skipBlock(BlockBegin block, final BlockBegin sux, BlockEnd oldEnd) {
+        final FrameState oldState = oldEnd.stateAfter();
+        assert sux.stateBefore().scope() == oldState.scope();
+        boolean hasAtLeastOnePhi = block.stateBefore().forEachPhi(block, new PhiProcedure() {
+            public boolean doPhi(Phi phi) {
+                return false;
+            }
+        });
+
+        if (hasAtLeastOnePhi) {
+            // can't skip a block that has phis
+            return;
+        }
+        for (final BlockBegin pred : block.predecessors()) {
+            final FrameState predState = pred.end().stateAfter();
+            if (predState.scope() != oldState.scope() || predState.stackSize() != oldState.stackSize()) {
+                // scopes would not match after skipping this block
+                // XXX: if phi's were smarter about scopes, this would not be necessary
+                return;
+            }
+            boolean atLeastOneSuxPhiMergesFromAnotherBlock = !sux.stateBefore().forEachPhi(sux, new PhiProcedure() {
+                public boolean doPhi(Phi phi) {
+                    if (phi.inputIn(sux.stateBefore()) != phi.inputIn(pred.end().stateAfter())) {
+                        return false;
+                    }
+                    return true;
+                }
+            });
+
+            if (atLeastOneSuxPhiMergesFromAnotherBlock) {
+                return;
+            }
+        }
+        ir.replaceBlock(block, sux);
+        C1XMetrics.BlocksSkipped++;
+    }
+
+    private void mergeBlocks(BlockBegin block, BlockBegin sux, BlockEnd oldEnd) {
+        BlockEnd newEnd;
+        // find instruction before oldEnd & append first instruction of sux block
+        Instruction prev = oldEnd.prev(block);
+        Instruction next = sux.next();
+        assert !(prev instanceof BlockEnd) : "must not be a BlockEnd";
+        prev.setNext(next, next.bci());
+        BlockUtil.disconnectFromGraph(sux);
+        newEnd = sux.end();
+        block.setEnd(newEnd);
+        // add exception handlers of deleted block, if any
+        for (BlockBegin xhandler : sux.exceptionHandlerBlocks()) {
+            block.addExceptionHandler(xhandler);
+
+            // also substitute predecessor of exception handler
+            assert xhandler.isPredecessor(sux) : "missing predecessor";
+            xhandler.removePredecessor(sux);
+            if (!xhandler.isPredecessor(block)) {
+                xhandler.addPredecessor(block);
+            }
+        }
+    }
+}