Mercurial > hg > graal-compiler

changeset 22598:5396006b321a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
TraceRA: always insert spill-moves and use TraceLinearScanResolveDataFlowPhase only for SSI resolution.
author Josef Eisl <josef.eisl@jku.at>
date Tue, 08 Sep 2015 10:50:21 +0200
parents 9fd19e2fc0be
children b83f27f75684
files graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java
diffstat 3 files changed, 77 insertions(+), 102 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java	Mon Sep 07 17:38:39 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java	Tue Sep 08 10:50:21 2015 +0200
@@ -726,7 +726,7 @@
     }
 
     protected TraceLinearScanResolveDataFlowPhase createResolveDataFlowPhase() {
-        return new TraceLinearScanResolveDataFlowPhase(this);
+        return new TraceLinearScanResolveDataFlowPhase(this, traceBuilderResult);
     }
 
     protected TraceLinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java	Mon Sep 07 17:38:39 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java	Tue Sep 08 10:50:21 2015 +0200
@@ -32,6 +32,7 @@
 import jdk.internal.jvmci.meta.*;
 
 import com.oracle.graal.compiler.common.alloc.*;
+import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult;
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.lir.*;
@@ -48,45 +49,21 @@
  */
 final class TraceLinearScanResolveDataFlowPhase extends AllocationPhase {
 
-    protected final TraceLinearScan allocator;
+    private final TraceLinearScan allocator;
+    private final TraceBuilderResult<?> traceBuilderResult;
 
-    protected TraceLinearScanResolveDataFlowPhase(TraceLinearScan allocator) {
+    protected TraceLinearScanResolveDataFlowPhase(TraceLinearScan allocator, TraceBuilderResult<?> traceBuilderResult) {
         this.allocator = allocator;
+        this.traceBuilderResult = traceBuilderResult;
     }
 
     @Override
     protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory,
                     RegisterAllocationConfig registerAllocationConfig) {
-        resolveDataFlow();
+        resolveDataFlow(allocator.sortedBlocks());
     }
 
-    protected void resolveCollectMappings0(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, TraceLocalMoveResolver moveResolver) {
-        assert moveResolver.checkEmpty();
-        assert midBlock == null ||
-                        (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors().get(0).equals(fromBlock) && midBlock.getSuccessors().get(0).equals(
-                                        toBlock));
-
-        int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock);
-        int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1;
-        int numOperands = allocator.operandSize();
-        BitSet liveAtEdge = allocator.getBlockData(toBlock).liveIn;
-
-        // visit all variables for which the liveAtEdge bit is set
-        for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) {
-            assert operandNum < numOperands : "live information set for not exisiting interval";
-            assert allocator.getBlockData(fromBlock).liveOut.get(operandNum) && allocator.getBlockData(toBlock).liveIn.get(operandNum) : "interval not live at this edge";
-
-            TraceInterval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF);
-            TraceInterval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF);
-
-            if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) {
-                // need to insert move instruction
-                moveResolver.addMapping(fromInterval, toInterval);
-            }
-        }
-    }
-
-    void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) {
+    private void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) {
         if (fromBlock.getSuccessorCount() <= 1) {
             if (Debug.isLogEnabled()) {
                 Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId());
@@ -128,79 +105,52 @@
      * have been split.
      */
     @SuppressWarnings("try")
-    protected void resolveDataFlow() {
+    private void resolveDataFlow(List<? extends AbstractBlockBase<?>> blocks) {
+        if (blocks.size() < 2) {
+            // no resolution necessary
+            return;
+        }
         try (Indent indent = Debug.logAndIndent("resolve data flow")) {
 
             TraceLocalMoveResolver moveResolver = allocator.createMoveResolver();
-            BitSet blockCompleted = new BitSet(allocator.blockCount());
-
-            BitSet alreadyResolved = new BitSet(allocator.blockCount());
-            for (AbstractBlockBase<?> fromBlock : allocator.sortedBlocks()) {
-                if (!blockCompleted.get(fromBlock.getLinearScanNumber())) {
-                    alreadyResolved.clear();
-                    alreadyResolved.or(blockCompleted);
-
-                    for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) {
-
-                        /*
-                         * Check for duplicate edges between the same blocks (can happen with switch
-                         * blocks).
-                         */
-                        if (!alreadyResolved.get(toBlock.getLinearScanNumber())) {
-                            if (Debug.isLogEnabled()) {
-                                Debug.log("processing edge between B%d and B%d", fromBlock.getId(), toBlock.getId());
-                            }
-
-                            alreadyResolved.set(toBlock.getLinearScanNumber());
-
-                            // collect all intervals that have been split between
-                            // fromBlock and toBlock
-                            resolveCollectMappings(fromBlock, toBlock, null, moveResolver);
-                            if (moveResolver.hasMappings()) {
-                                resolveFindInsertPos(fromBlock, toBlock, moveResolver);
-                                moveResolver.resolveAndAppendMoves();
-                            }
-                        }
-                    }
+            ListIterator<? extends AbstractBlockBase<?>> it = blocks.listIterator();
+            AbstractBlockBase<?> toBlock = null;
+            for (AbstractBlockBase<?> fromBlock = it.next(); it.hasNext(); fromBlock = toBlock) {
+                toBlock = it.next();
+                assert containedInTrace(fromBlock) : "Not in Trace: " + fromBlock;
+                assert containedInTrace(toBlock) : "Not in Trace: " + toBlock;
+                resolveCollectMappings(fromBlock, toBlock, moveResolver);
+            }
+            assert blocks.get(blocks.size() - 1).equals(toBlock);
+            if (toBlock.isLoopEnd()) {
+                assert toBlock.getSuccessorCount() == 1;
+                AbstractBlockBase<?> loopHeader = toBlock.getSuccessors().get(0);
+                if (containedInTrace(loopHeader)) {
+                    resolveCollectMappings(toBlock, loopHeader, moveResolver);
                 }
             }
 
         }
     }
 
-    protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, TraceLocalMoveResolver moveResolver) {
-        assert midBlock == null;
-        if (containedInTrace(fromBlock) && containedInTrace(toBlock)) {
-            assert moveResolver.checkEmpty();
-            assert midBlock == null ||
-                            (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors().get(0).equals(fromBlock) && midBlock.getSuccessors().get(0).equals(
-                                            toBlock));
-
-            int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock);
-            int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1;
-            int numOperands = allocator.operandSize();
-            BitSet liveAtEdge = allocator.getBlockData(toBlock).liveIn;
-
-            // visit all variables for which the liveAtEdge bit is set
-            for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) {
-                assert operandNum < numOperands : "live information set for not exisiting interval";
-                assert allocator.getBlockData(fromBlock).liveOut.get(operandNum) && allocator.getBlockData(toBlock).liveIn.get(operandNum) : "interval not live at this edge";
-
-                TraceInterval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF);
-                TraceInterval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF);
-
-                if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) {
-                    // need to insert move instruction
-                    moveResolver.addMapping(fromInterval, toInterval);
-                }
+    private void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) {
+        try (Indent indent0 = Debug.logAndIndent("Edge %s -> %s", fromBlock, toBlock)) {
+            // collect all intervals that have been split between
+            // fromBlock and toBlock
+            SSIUtil.forEachValuePair(allocator.getLIR(), toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock));
+            if (moveResolver.hasMappings()) {
+                resolveFindInsertPos(fromBlock, toBlock, moveResolver);
+                moveResolver.resolveAndAppendMoves();
             }
-            SSIUtil.forEachValuePair(allocator.getLIR(), toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock));
         }
-
     }
 
     private boolean containedInTrace(AbstractBlockBase<?> block) {
-        return allocator.sortedBlocks().contains(block);
+        return currentTrace() == traceBuilderResult.getTraceForBlock(block);
+    }
+
+    private int currentTrace() {
+        return traceBuilderResult.getTraceForBlock(allocator.sortedBlocks().get(0));
     }
 
     private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]");
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java	Mon Sep 07 17:38:39 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java	Tue Sep 08 10:50:21 2015 +0200
@@ -37,6 +37,8 @@
 import com.oracle.graal.compiler.common.util.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.StandardOp.BlockEndOp;
+import com.oracle.graal.lir.StandardOp.LabelOp;
 import com.oracle.graal.lir.StandardOp.ValueMoveOp;
 import com.oracle.graal.lir.alloc.lsra.*;
 import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterPriority;
@@ -233,6 +235,26 @@
         }
     }
 
+    private int insertIdAtBasicBlockBoundary(int opId) {
+        assert allocator.isBlockBegin(opId) : "Not a block begin: " + opId;
+        assert allocator.instructionForId(opId) instanceof LabelOp;
+        assert allocator.instructionForId(opId - 2) instanceof BlockEndOp;
+
+        AbstractBlockBase<?> toBlock = allocator.blockForId(opId);
+        AbstractBlockBase<?> fromBlock = allocator.blockForId(opId - 2);
+
+        final int operandId;
+        if (fromBlock.getSuccessorCount() == 1) {
+            // insert move in predecessor
+            operandId = opId - 2;
+        } else {
+            assert toBlock.getPredecessorCount() == 1 : String.format("Critical Edge? %s->%s", fromBlock, toBlock);
+            // insert move in predecessor
+            operandId = opId + 2;
+        }
+        return operandId;
+    }
+
     private void insertMove(int operandId, TraceInterval srcIt, TraceInterval dstIt) {
         // output all moves here. When source and target are equal, the move is
         // optimized away later in assignRegNums
@@ -335,12 +357,13 @@
             // must calculate this before the actual split is performed and before split position is
             // moved to odd opId
             boolean isBlockBegin = allocator.isBlockBegin(optimalSplitPos);
-            boolean moveNecessary = !isBlockBegin;
+            boolean moveNecessary = true;
 
-            if (!isBlockBegin) {
-                // move position before actual instruction (odd opId)
-                optimalSplitPos = (optimalSplitPos - 1) | 1;
+            if (isBlockBegin) {
+                optimalSplitPos = insertIdAtBasicBlockBoundary(optimalSplitPos);
             }
+            // move position before actual instruction (odd opId)
+            optimalSplitPos = (optimalSplitPos - 1) | 1;
 
             if (Debug.isLogEnabled()) {
                 Debug.log("splitting at position %d", optimalSplitPos);
@@ -434,10 +457,11 @@
                 assert optimalSplitPos < interval.to() : "cannot split at end of interval";
                 assert optimalSplitPos >= interval.from() : "cannot split before start of interval";
 
-                if (!allocator.isBlockBegin(optimalSplitPos)) {
-                    // move position before actual instruction (odd opId)
-                    optimalSplitPos = (optimalSplitPos - 1) | 1;
+                if (allocator.isBlockBegin(optimalSplitPos)) {
+                    optimalSplitPos = insertIdAtBasicBlockBoundary(optimalSplitPos);
                 }
+                // move position before actual instruction (odd opId)
+                optimalSplitPos = (optimalSplitPos - 1) | 1;
 
                 try (Indent indent2 = Debug.logAndIndent("splitting at position %d", optimalSplitPos)) {
                     assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary";
@@ -448,12 +472,13 @@
                     handleSpillSlot(spilledPart);
                     changeSpillState(spilledPart, optimalSplitPos);
 
-                    if (!allocator.isBlockBegin(optimalSplitPos)) {
-                        if (Debug.isLogEnabled()) {
-                            Debug.log("inserting move from interval %d to %d", interval.operandNumber, spilledPart.operandNumber);
-                        }
-                        insertMove(optimalSplitPos, interval, spilledPart);
+                    if (allocator.isBlockBegin(optimalSplitPos)) {
+                        optimalSplitPos = insertIdAtBasicBlockBoundary(optimalSplitPos);
                     }
+                    if (Debug.isLogEnabled()) {
+                        Debug.log("inserting move from interval %s to %d", interval, spilledPart);
+                    }
+                    insertMove(optimalSplitPos, interval, spilledPart);
 
                     // the currentSplitChild is needed later when moves are inserted for reloading
                     assert spilledPart.currentSplitChild() == interval : "overwriting wrong currentSplitChild";