changeset 22548:44c517c8ba62

TraceRA: remove OptimizingLinearScanWalker.
author Josef Eisl <josef.eisl@jku.at>
date Mon, 31 Aug 2015 13:23:04 +0200
parents 544f172cb2db
children 8021143052af
files graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanRegisterAllocationPhase.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/OptimizingLinearScanWalker.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java
diffstat 3 files changed, 4 insertions(+), 258 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanRegisterAllocationPhase.java	Mon Aug 31 13:21:01 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanRegisterAllocationPhase.java	Mon Aug 31 13:23:04 2015 +0200
@@ -59,12 +59,7 @@
             notPrecoloredIntervals = result.second;
 
             // allocate cpu registers
-            LinearScanWalker lsw;
-            if (com.oracle.graal.lir.alloc.lsra.OptimizingLinearScanWalker.Options.LSRAOptimization.getValue()) {
-                lsw = new OptimizingLinearScanWalker(allocator, precoloredIntervals, notPrecoloredIntervals);
-            } else {
-                lsw = new LinearScanWalker(allocator, precoloredIntervals, notPrecoloredIntervals);
-            }
+            LinearScanWalker lsw = new LinearScanWalker(allocator, precoloredIntervals, notPrecoloredIntervals);
             lsw.walk();
             lsw.finishAllocation();
         }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/OptimizingLinearScanWalker.java	Mon Aug 31 13:21:01 2015 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,242 +0,0 @@
-/*
- * Copyright (c) 2014, 2014, 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.alloc.trace;
-
-import static jdk.internal.jvmci.code.ValueUtil.*;
-import jdk.internal.jvmci.code.*;
-import jdk.internal.jvmci.meta.*;
-
-import com.oracle.graal.compiler.common.cfg.*;
-import com.oracle.graal.debug.*;
-import com.oracle.graal.debug.Debug.Scope;
-import com.oracle.graal.lir.alloc.trace.Interval.RegisterBinding;
-import com.oracle.graal.lir.alloc.trace.Interval.RegisterBindingLists;
-import com.oracle.graal.lir.alloc.trace.Interval.RegisterPriority;
-import com.oracle.graal.lir.alloc.trace.Interval.State;
-
-public class OptimizingLinearScanWalker extends LinearScanWalker {
-
-    OptimizingLinearScanWalker(TraceLinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) {
-        super(allocator, unhandledFixedFirst, unhandledAnyFirst);
-    }
-
-    @Override
-    protected void handleSpillSlot(Interval interval) {
-        assert interval.location() != null : "interval  not assigned " + interval;
-        if (interval.canMaterialize()) {
-            assert !isStackSlotValue(interval.location()) : "interval can materialize but assigned to a stack slot " + interval;
-            return;
-        }
-        assert isStackSlotValue(interval.location()) : "interval not assigned to a stack slot " + interval;
-        try (Scope s1 = Debug.scope("LSRAOptimization")) {
-            Debug.log("adding stack to unhandled list %s", interval);
-            unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Stack, interval);
-        }
-    }
-
-    @SuppressWarnings("unused")
-    private static void printRegisterBindingList(RegisterBindingLists list, RegisterBinding binding) {
-        for (Interval interval = list.get(binding); interval != Interval.EndMarker; interval = interval.next) {
-            Debug.log("%s", interval);
-        }
-    }
-
-    @Override
-    void walk() {
-        try (Scope s = Debug.scope("OptimizingLinearScanWalker")) {
-            for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
-                optimizeBlock(block);
-            }
-        }
-        super.walk();
-    }
-
-    private void optimizeBlock(AbstractBlockBase<?> block) {
-        if (block.getPredecessorCount() == 1) {
-            int nextBlock = allocator.getFirstLirInstructionId(block);
-            try (Scope s1 = Debug.scope("LSRAOptimization")) {
-                Debug.log("next block: %s (%d)", block, nextBlock);
-            }
-            try (Indent indent0 = Debug.indent()) {
-                walkTo(nextBlock);
-
-                try (Scope s1 = Debug.scope("LSRAOptimization")) {
-                    boolean changed = true;
-                    // we need to do this because the active lists might change
-                    loop: while (changed) {
-                        changed = false;
-                        try (Indent indent1 = Debug.logAndIndent("Active intervals: (block %s [%d])", block, nextBlock)) {
-                            for (Interval active = activeLists.get(RegisterBinding.Any); active != Interval.EndMarker; active = active.next) {
-                                Debug.log("active   (any): %s", active);
-                                if (optimize(nextBlock, block, active, RegisterBinding.Any)) {
-                                    changed = true;
-                                    break loop;
-                                }
-                            }
-                            for (Interval active = activeLists.get(RegisterBinding.Stack); active != Interval.EndMarker; active = active.next) {
-                                Debug.log("active (stack): %s", active);
-                                if (optimize(nextBlock, block, active, RegisterBinding.Stack)) {
-                                    changed = true;
-                                    break loop;
-                                }
-                            }
-                        }
-                    }
-                }
-            }
-        }
-    }
-
-    private boolean optimize(int currentPos, AbstractBlockBase<?> currentBlock, Interval currentInterval, RegisterBinding binding) {
-        // BEGIN initialize and sanity checks
-        assert currentBlock != null : "block must not be null";
-        assert currentInterval != null : "interval must not be null";
-
-        assert currentBlock.getPredecessorCount() == 1 : "more than one predecessors -> optimization not possible";
-
-        if (!currentInterval.isSplitChild()) {
-            // interval is not a split child -> no need for optimization
-            return false;
-        }
-
-        if (currentInterval.from() == currentPos) {
-            // the interval starts at the current position so no need for splitting
-            return false;
-        }
-
-        // get current location
-        AllocatableValue currentLocation = currentInterval.location();
-        assert currentLocation != null : "active intervals must have a location assigned!";
-
-        // get predecessor stuff
-        AbstractBlockBase<?> predecessorBlock = currentBlock.getPredecessors().get(0);
-        int predEndId = allocator.getLastLirInstructionId(predecessorBlock);
-        Interval predecessorInterval = currentInterval.getIntervalCoveringOpId(predEndId);
-        assert predecessorInterval != null : "variable not live at the end of the only predecessor! " + predecessorBlock + " -> " + currentBlock + " interval: " + currentInterval;
-        AllocatableValue predecessorLocation = predecessorInterval.location();
-        assert predecessorLocation != null : "handled intervals must have a location assigned!";
-
-        // END initialize and sanity checks
-
-        if (currentLocation.equals(predecessorLocation)) {
-            // locations are already equal -> nothing to optimize
-            return false;
-        }
-
-        if (!isStackSlotValue(predecessorLocation) && !isRegister(predecessorLocation)) {
-            assert predecessorInterval.canMaterialize();
-            // value is materialized -> no need for optimization
-            return false;
-        }
-
-        assert isStackSlotValue(currentLocation) || isRegister(currentLocation) : "current location not a register or stack slot " + currentLocation;
-
-        try (Indent indent = Debug.logAndIndent("location differs: %s vs. %s", predecessorLocation, currentLocation)) {
-            // split current interval at current position
-            Debug.log("splitting at position %d", currentPos);
-
-            assert allocator.isBlockBegin(currentPos) && ((currentPos & 1) == 0) : "split pos must be even when on block boundary";
-
-            Interval splitPart = currentInterval.split(currentPos, allocator);
-            activeLists.remove(binding, currentInterval);
-
-            assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position";
-
-            // the currentSplitChild is needed later when moves are inserted for reloading
-            assert splitPart.currentSplitChild() == currentInterval : "overwriting wrong currentSplitChild";
-            splitPart.makeCurrentSplitChild();
-
-            if (Debug.isLogEnabled()) {
-                Debug.log("left interval  : %s", currentInterval.logString(allocator));
-                Debug.log("right interval : %s", splitPart.logString(allocator));
-            }
-
-            if (com.oracle.graal.lir.alloc.lsra.OptimizingLinearScanWalker.Options.LSRAOptSplitOnly.getValue()) {
-                // just add the split interval to the unhandled list
-                unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Any, splitPart);
-            } else {
-                if (isRegister(predecessorLocation)) {
-                    splitRegisterInterval(splitPart, asRegister(predecessorLocation));
-                } else {
-                    assert isStackSlotValue(predecessorLocation);
-                    Debug.log("assigning interval %s to %s", splitPart, predecessorLocation);
-                    splitPart.assignLocation(predecessorLocation);
-                    // activate interval
-                    activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Stack, splitPart);
-                    splitPart.state = State.Active;
-
-                    splitStackInterval(splitPart);
-                }
-            }
-        }
-        return true;
-    }
-
-    private void splitRegisterInterval(Interval interval, Register reg) {
-        // collect current usage of registers
-        initVarsForAlloc(interval);
-        initUseLists(false);
-        spillExcludeActiveFixed();
-        // spillBlockUnhandledFixed(cur);
-        assert unhandledLists.get(RegisterBinding.Fixed) == Interval.EndMarker : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0";
-        spillBlockInactiveFixed(interval);
-        spillCollectActiveAny(RegisterPriority.LiveAtLoopEnd);
-        spillCollectInactiveAny(interval);
-
-        if (Debug.isLogEnabled()) {
-            try (Indent indent2 = Debug.logAndIndent("state of registers:")) {
-                for (Register register : availableRegs) {
-                    int i = register.number;
-                    try (Indent indent3 = Debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, intervals: ", i, usePos[i], blockPos[i])) {
-                        for (int j = 0; j < spillIntervals[i].size(); j++) {
-                            Debug.log("%d ", spillIntervals[i].get(j).operandNumber);
-                        }
-                    }
-                }
-            }
-        }
-
-        // the register must be free at least until this position
-        boolean needSplit = blockPos[reg.number] <= interval.to();
-
-        int splitPos = blockPos[reg.number];
-
-        assert splitPos > 0 : "invalid splitPos";
-        assert needSplit || splitPos > interval.from() : "splitting interval at from";
-
-        Debug.log("assigning interval %s to %s", interval, reg);
-        interval.assignLocation(reg.asValue(interval.kind()));
-        if (needSplit) {
-            // register not available for full interval : so split it
-            splitWhenPartialRegisterAvailable(interval, splitPos);
-        }
-
-        // perform splitting and spilling for all affected intervals
-        splitAndSpillIntersectingIntervals(reg);
-
-        // activate interval
-        activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Any, interval);
-        interval.state = State.Active;
-
-    }
-}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java	Mon Aug 31 13:21:01 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java	Mon Aug 31 13:23:04 2015 +0200
@@ -34,7 +34,6 @@
 import jdk.internal.jvmci.common.*;
 import jdk.internal.jvmci.meta.*;
 import jdk.internal.jvmci.options.*;
-import jdk.internal.jvmci.options.OptionValue.OverrideScope;
 
 import com.oracle.graal.compiler.common.alloc.*;
 import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult;
@@ -70,8 +69,8 @@
         /**
          * Bit map specifying which operands are live upon entry to this block. These are values
          * used in this block or any of its successors where such value are not defined in this
-         * block. The bit index of an operand is its {@linkplain TraceLinearScan#operandNumber(Value)
-         * operand number}.
+         * block. The bit index of an operand is its
+         * {@linkplain TraceLinearScan#operandNumber(Value) operand number}.
          */
         public BitSet liveIn;
 
@@ -632,13 +631,7 @@
             try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals())) {
                 sortIntervalsBeforeAllocation();
 
-                try (OverrideScope os = OptionValue.override(com.oracle.graal.lir.alloc.lsra.OptimizingLinearScanWalker.Options.LSRAOptimization, false)) {
-                    /*
-                     * No need for single predecessor block optimization as this is inherently done
-                     * by the trace approach.
-                     */
-                    createRegisterAllocationPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
-                }
+                createRegisterAllocationPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
 
                 if (com.oracle.graal.lir.alloc.lsra.LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue()) {
                     createOptimizeSpillPositionPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);