# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1420992931 -3600
# Node ID ade7699e160e24cb2d16432948900fcd687253d8
# Parent  42d1f20e54ea638f0c11775a2a64e55f79bd3c3c
Calculate blocks immediately in correct order.

diff -r 42d1f20e54ea -r ade7699e160e graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java
--- a/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java	Sun Jan 11 16:26:26 2015 +0100
+++ b/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java	Sun Jan 11 17:15:31 2015 +0100
@@ -60,7 +60,7 @@
         BitSet bitSet;
 
         public BciBlockBitMap(BciBlockMapping blockMap) {
-            bitSet = new BitSet(blockMap.blocks.size());
+            bitSet = new BitSet(blockMap.getBlocks().length);
         }
 
         public boolean get(BciBlock block) {
@@ -104,7 +104,7 @@
             liveness = blockMap.liveness;
             blockVisited = new BciBlockBitMap(blockMap);
             // add predecessors
-            for (BciBlock block : blockMap.blocks) {
+            for (BciBlock block : blockMap.getBlocks()) {
                 for (BciBlock successor : block.getSuccessors()) {
                     successor.getPredecessors().add(block);
                 }
@@ -129,8 +129,8 @@
             BaselineControlFlowGraph cfg = BaselineControlFlowGraph.compute(blockMap);
 
             // create the LIR
-            List<? extends AbstractBlock<?>> linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blockMap.blocks.size(), blockMap.startBlock);
-            List<? extends AbstractBlock<?>> codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blockMap.blocks.size(), blockMap.startBlock);
+            List<? extends AbstractBlock<?>> linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blockMap.getBlocks().length, blockMap.startBlock);
+            List<? extends AbstractBlock<?>> codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blockMap.getBlocks().length, blockMap.startBlock);
             LIR lir = new LIR(cfg, linearScanOrder, codeEmittingOrder);
 
             RegisterConfig registerConfig = null;
@@ -147,7 +147,7 @@
 
                     // possibly add all the arguments to slots in the local variable array
 
-                    for (BciBlock block : blockMap.blocks) {
+                    for (BciBlock block : blockMap.getBlocks()) {
                         emitBlock(block);
                     }
 
diff -r 42d1f20e54ea -r ade7699e160e graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineControlFlowGraph.java
--- a/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineControlFlowGraph.java	Sun Jan 11 16:26:26 2015 +0100
+++ b/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineControlFlowGraph.java	Sun Jan 11 17:15:31 2015 +0100
@@ -32,7 +32,7 @@
 
 public final class BaselineControlFlowGraph implements AbstractControlFlowGraph<BciBlock> {
 
-    private List<BciBlock> blocks;
+    private BciBlock[] blocks;
     private Collection<Loop<BciBlock>> loops;
 
     public static BaselineControlFlowGraph compute(BciBlockMapping blockMap) {
@@ -50,12 +50,12 @@
     }
 
     private BaselineControlFlowGraph(BciBlockMapping blockMap) {
-        blocks = blockMap.blocks;
+        blocks = blockMap.getBlocks();
         loops = new ArrayList<>();
     }
 
     public List<BciBlock> getBlocks() {
-        return blocks;
+        return Arrays.asList(blocks);
     }
 
     public Collection<Loop<BciBlock>> getLoops() {
@@ -63,8 +63,8 @@
     }
 
     public BciBlock getStartBlock() {
-        if (!blocks.isEmpty()) {
-            return blocks.get(0);
+        if (blocks.length > 0) {
+            return blocks[0];
         }
         return null;
     }
diff -r 42d1f20e54ea -r ade7699e160e graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java	Sun Jan 11 16:26:26 2015 +0100
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java	Sun Jan 11 17:15:31 2015 +0100
@@ -336,7 +336,7 @@
     /**
      * The blocks found in this method, in reverse postorder.
      */
-    public final List<BciBlock> blocks;
+    private BciBlock[] blocks;
     public final ResolvedJavaMethod method;
     public boolean hasJsrBytecodes;
     public BciBlock startBlock;
@@ -351,6 +351,7 @@
 
     private final boolean doLivenessAnalysis;
     public LocalLiveness liveness;
+    private int blocksNotYetAssignedId;
 
     /**
      * Creates a new BlockMap instance from bytecode of the given method .
@@ -364,7 +365,10 @@
         this.stream = new BytecodeStream(method.getCode());
         int codeSize = method.getCodeSize();
         this.blockMap = new BciBlock[codeSize];
-        this.blocks = new ArrayList<>();
+    }
+
+    public BciBlock[] getBlocks() {
+        return this.blocks;
     }
 
     /**
@@ -385,8 +389,6 @@
         computeBlockOrder();
         fixLoopBits();
 
-        initializeBlockIds();
-
         startBlock = blockMap[0];
 
         assert verify();
@@ -408,7 +410,7 @@
 
     private boolean verify() {
         for (BciBlock block : blocks) {
-            assert blocks.get(block.getId()) == block;
+            assert blocks[block.getId()] == block;
 
             for (int i = 0; i < block.getSuccessorCount(); i++) {
                 BciBlock sux = block.getSuccessor(i);
@@ -421,12 +423,6 @@
         return true;
     }
 
-    private void initializeBlockIds() {
-        for (int i = 0; i < blocks.size(); i++) {
-            blocks.get(i).setId(i);
-        }
-    }
-
     private void makeExceptionEntries() {
         // start basic blocks at all exception handler blocks and mark them as exception entries
         for (ExceptionHandler h : this.exceptionHandlers) {
@@ -575,6 +571,7 @@
         BciBlock oldBlock = blockMap[startBci];
         if (oldBlock == null) {
             BciBlock newBlock = new BciBlock();
+            blocksNotYetAssignedId++;
             newBlock.startBci = startBci;
             blockMap[startBci] = newBlock;
             return newBlock;
@@ -583,6 +580,7 @@
             // Backward branch into the middle of an already processed block.
             // Add the correct fall-through successor.
             BciBlock newBlock = new BciBlock();
+            blocksNotYetAssignedId++;
             newBlock.startBci = startBci;
             newBlock.endBci = oldBlock.endBci;
             newBlock.getSuccessors().addAll(oldBlock.getSuccessors());
@@ -692,6 +690,7 @@
                 ExceptionDispatchBlock curHandler = exceptionDispatch.get(h);
                 if (curHandler == null) {
                     curHandler = new ExceptionDispatchBlock();
+                    blocksNotYetAssignedId++;
                     curHandler.startBci = -1;
                     curHandler.endBci = -1;
                     curHandler.deoptBci = bci;
@@ -731,18 +730,33 @@
     }
 
     private void computeBlockOrder() {
+        this.blocks = new BciBlock[blocksNotYetAssignedId];
         long loop = computeBlockOrder(blockMap[0]);
 
         if (loop != 0) {
             // There is a path from a loop end to the method entry that does not pass the loop
-            // header.
-            // Therefore, the loop is non reducible (has more than one entry).
+            // header. Therefore, the loop is non reducible (has more than one entry).
             // We don't want to compile such methods because the IR only supports structured loops.
             throw new BailoutException("Non-reducible loop");
         }
 
-        // Convert postorder to the desired reverse postorder.
-        Collections.reverse(blocks);
+        if (blocks[0] == null) {
+            purgeLeadingNullBlocks();
+        }
+    }
+
+    private void purgeLeadingNullBlocks() {
+        // Purge leading null values due to unreachable blocks.
+        int i = 0;
+        for (; i < blocks.length; ++i) {
+            if (blocks[i] != null) {
+                break;
+            }
+        }
+        blocks = Arrays.copyOfRange(blocks, i, blocks.length);
+        for (i = 0; i < blocks.length; ++i) {
+            blocks[i].setId(i);
+        }
     }
 
     public void log(String name) {
@@ -751,10 +765,10 @@
             StringBuilder sb = new StringBuilder(Debug.currentScope()).append("BlockMap ").append(name).append(" :");
             sb.append(n);
             Iterable<BciBlock> it;
-            if (blocks.isEmpty()) {
+            if (blocks == null) {
                 it = new HashSet<>(Arrays.asList(blockMap));
             } else {
-                it = blocks;
+                it = Arrays.asList(blocks);
             }
             for (BciBlock b : it) {
                 if (b == null) {
@@ -875,7 +889,9 @@
         }
 
         block.active = false;
-        blocks.add(block);
+        blocksNotYetAssignedId--;
+        blocks[blocksNotYetAssignedId] = block;
+        block.setId(blocksNotYetAssignedId);
 
         return loops;
     }
@@ -925,8 +941,8 @@
             do {
                 Debug.log("Iteration %d", iteration);
                 changed = false;
-                for (int i = blocks.size() - 1; i >= 0; i--) {
-                    BciBlock block = blocks.get(i);
+                for (int i = blocks.length - 1; i >= 0; i--) {
+                    BciBlock block = blocks[i];
                     int blockID = block.getId();
                     // log statements in IFs because debugLiveX creates a new String
                     if (Debug.isLogEnabled()) {
@@ -1152,7 +1168,7 @@
         private final long[] localsLiveKill;
 
         public SmallLocalLiveness() {
-            int blockSize = blocks.size();
+            int blockSize = blocks.length;
             localsLiveIn = new long[blockSize];
             localsLiveOut = new long[blockSize];
             localsLiveGen = new long[blockSize];
@@ -1245,11 +1261,12 @@
         private BitSet[] localsLiveKill;
 
         public LargeLocalLiveness() {
-            localsLiveIn = new BitSet[blocks.size()];
-            localsLiveOut = new BitSet[blocks.size()];
-            localsLiveGen = new BitSet[blocks.size()];
-            localsLiveKill = new BitSet[blocks.size()];
-            for (int i = 0; i < blocks.size(); i++) {
+            int blocksSize = blocks.length;
+            localsLiveIn = new BitSet[blocksSize];
+            localsLiveOut = new BitSet[blocksSize];
+            localsLiveGen = new BitSet[blocksSize];
+            localsLiveKill = new BitSet[blocksSize];
+            for (int i = 0; i < blocksSize; i++) {
                 localsLiveIn[i] = new BitSet(method.getMaxLocals());
                 localsLiveOut[i] = new BitSet(method.getMaxLocals());
                 localsLiveGen[i] = new BitSet(method.getMaxLocals());
diff -r 42d1f20e54ea -r ade7699e160e graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Sun Jan 11 16:26:26 2015 +0100
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Sun Jan 11 17:15:31 2015 +0100
@@ -265,7 +265,7 @@
                         blockMap.startBlock.firstInstruction = lastInstr;
                     }
 
-                    for (BciBlock block : blockMap.blocks) {
+                    for (BciBlock block : blockMap.getBlocks()) {
                         processBlock(block);
                     }
                     processBlock(unwindBlock);
diff -r 42d1f20e54ea -r ade7699e160e graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Sun Jan 11 16:26:26 2015 +0100
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Sun Jan 11 17:15:31 2015 +0100
@@ -74,7 +74,7 @@
     public void printCFG(String label, BciBlockMapping blockMap) {
         begin("cfg");
         out.print("name \"").print(label).println('"');
-        for (BciBlockMapping.BciBlock block : blockMap.blocks) {
+        for (BciBlockMapping.BciBlock block : blockMap.getBlocks()) {
             begin("block");
             printBlock(block);
             end("block");