# HG changeset patch # User Christian Wimmer # Date 1326927843 28800 # Node ID 1e3ecb08767d07a540666339269744efebdcff70 # Parent 600cbdce98056d0612484d524f88e293422b6390 Output of lifetime intervals for new register allocator diff -r 600cbdce9805 -r 1e3ecb08767d graal/com.oracle.max.cri/src/com/oracle/max/cri/ci/CiStackSlot.java --- a/graal/com.oracle.max.cri/src/com/oracle/max/cri/ci/CiStackSlot.java Wed Jan 18 18:21:52 2012 +0100 +++ b/graal/com.oracle.max.cri/src/com/oracle/max/cri/ci/CiStackSlot.java Wed Jan 18 15:04:03 2012 -0800 @@ -124,7 +124,7 @@ } else if (offset >= 0) { return "in:" + offset + kindSuffix(); } else { - return "spill:" + (-offset) + kindSuffix(); + return "stack:" + (-offset) + kindSuffix(); } } diff -r 600cbdce9805 -r 1e3ecb08767d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/DataFlowAnalysis.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/DataFlowAnalysis.java Wed Jan 18 18:21:52 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/DataFlowAnalysis.java Wed Jan 18 15:04:03 2012 -0800 @@ -37,19 +37,16 @@ import com.oracle.max.graal.compiler.schedule.*; public class DataFlowAnalysis { - private final GraalContext context; private final LIR lir; private final RiRegisterConfig registerConfig; - public DataFlowAnalysis(GraalContext context, LIR lir, RiRegisterConfig registerConfig) { - this.context = context; + public DataFlowAnalysis(LIR lir, RiRegisterConfig registerConfig) { this.lir = lir; this.registerConfig = registerConfig; } public void execute() { numberInstructions(); - context.observable.fireCompilationEvent("After instruction numbering", lir); backwardDataFlow(); } diff -r 600cbdce9805 -r 1e3ecb08767d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/LinearScanAllocator.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/LinearScanAllocator.java Wed Jan 18 18:21:52 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/LinearScanAllocator.java Wed Jan 18 15:04:03 2012 -0800 @@ -52,7 +52,7 @@ this.lir = lir; this.frameMap = frameMap; - this.dataFlow = new DataFlowAnalysis(context, lir, frameMap.registerConfig); + this.dataFlow = new DataFlowAnalysis(lir, frameMap.registerConfig); this.blockBeginLocations = new LocationMap[lir.linearScanOrder().size()]; this.blockEndLocations = new LocationMap[lir.linearScanOrder().size()]; this.moveResolver = new MoveResolverImpl(frameMap); @@ -159,16 +159,17 @@ assert LIRVerifier.verify(true, lir, frameMap); dataFlow.execute(); + IntervalPrinter.printBeforeAllocation("Before register allocation", context, lir, frameMap.registerConfig, dataFlow); + allocate(); - context.observable.fireCompilationEvent("After linear scan allocation", lir); + IntervalPrinter.printAfterAllocation("After linear scan allocation", context, lir, frameMap.registerConfig, dataFlow, blockEndLocations); ResolveDataFlow resolveDataFlow = new ResolveDataFlowImpl(lir, moveResolver, dataFlow); resolveDataFlow.execute(); - frameMap.finish(); - context.observable.fireCompilationEvent("After resolve data flow", lir); + IntervalPrinter.printAfterAllocation("After resolve data flow", context, lir, frameMap.registerConfig, dataFlow, blockEndLocations); assert RegisterVerifier.verify(lir, frameMap); AssignRegisters assignRegisters = new AssignRegistersImpl(lir, frameMap); diff -r 600cbdce9805 -r 1e3ecb08767d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/SpillAllAllocator.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/SpillAllAllocator.java Wed Jan 18 18:21:52 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/SpillAllAllocator.java Wed Jan 18 15:04:03 2012 -0800 @@ -52,7 +52,7 @@ this.lir = lir; this.frameMap = frameMap; - this.dataFlow = new DataFlowAnalysis(context, lir, frameMap.registerConfig); + this.dataFlow = new DataFlowAnalysis(lir, frameMap.registerConfig); this.blockLocations = new LocationMap[lir.linearScanOrder().size()]; this.moveResolver = new MoveResolverImpl(frameMap); } @@ -134,15 +134,17 @@ assert LIRVerifier.verify(true, lir, frameMap); dataFlow.execute(); + IntervalPrinter.printBeforeAllocation("Before register allocation", context, lir, frameMap.registerConfig, dataFlow); + allocate(); - frameMap.finish(); - context.observable.fireCompilationEvent("After spill all allocation", lir); + IntervalPrinter.printAfterAllocation("After spill all allocation", context, lir, frameMap.registerConfig, dataFlow, blockLocations); ResolveDataFlow resolveDataFlow = new ResolveDataFlowImpl(lir, moveResolver, dataFlow); resolveDataFlow.execute(); + frameMap.finish(); - context.observable.fireCompilationEvent("After resolve data flow", lir); + IntervalPrinter.printAfterAllocation("After resolve data flow", context, lir, frameMap.registerConfig, dataFlow, blockLocations); assert RegisterVerifier.verify(lir, frameMap); AssignRegisters assignRegisters = new AssignRegistersImpl(lir, frameMap); diff -r 600cbdce9805 -r 1e3ecb08767d graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/IntervalPrinter.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/IntervalPrinter.java Wed Jan 18 15:04:03 2012 -0800 @@ -0,0 +1,279 @@ +/* + * Copyright (c) 2012, 2012, 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.max.graal.alloc.util; + +import static com.oracle.max.cri.ci.CiValueUtil.*; +import static com.oracle.max.graal.alloc.util.ValueUtil.*; + +import java.util.*; + +import com.oracle.max.cri.ci.*; +import com.oracle.max.cri.ri.*; +import com.oracle.max.graal.alloc.simple.*; +import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.lir.*; +import com.oracle.max.graal.compiler.lir.LIRInstruction.OperandFlag; +import com.oracle.max.graal.compiler.lir.LIRInstruction.OperandMode; +import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure; +import com.oracle.max.graal.compiler.lir.LIRPhiMapping.PhiValueProcedure; + +public final class IntervalPrinter { + + public static void printBeforeAllocation(String label, GraalContext context, LIR lir, RiRegisterConfig registerConfig, DataFlowAnalysis dataFlow) { + if (context.isObserved()) { + IntervalPrinter printer = new IntervalPrinter(lir, registerConfig, dataFlow, null); + context.observable.fireCompilationEvent(label, lir, printer.execute()); + } + } + + public static void printAfterAllocation(String label, GraalContext context, LIR lir, RiRegisterConfig registerConfig, DataFlowAnalysis dataFlow, LocationMap[] blockEndLocations) { + if (context.isObserved()) { + IntervalPrinter printer = new IntervalPrinter(lir, registerConfig, dataFlow, blockEndLocations); + context.observable.fireCompilationEvent(label, lir, printer.execute()); + } + } + + + public static class Range { + public final int from; + public final int to; + + public Range(int from, int to) { + this.from = from; + this.to = to; + } + } + + public static class UsePosition { + public final int pos; + public final String kind; + + public UsePosition(int pos, String kind) { + this.pos = pos; + this.kind = kind; + } + } + + public static class Interval { + public final String name; + public final String description; + public final String variable; + public final String type; + public final List ranges; + public final List uses; + + protected final int orderNum; + protected int lastTo; + + public Interval(int orderNum, String name, String description, String variable, String type) { + this.orderNum = orderNum; + this.name = name; + this.description = description; + this.variable = variable; + this.type = type; + this.ranges = new ArrayList<>(); + this.uses = new ArrayList<>(); + } + } + + + private final LIR lir; + private final RiRegisterConfig registerConfig; + private final DataFlowAnalysis dataFlow; + private final LocationMap[] blockEndLocations; + private final Variable[] variables; + private final Map intervals; + + private IntervalPrinter(LIR lir, RiRegisterConfig registerConfig, DataFlowAnalysis dataFlow, LocationMap[] blockEndLocations) { + this.lir = lir; + this.registerConfig = registerConfig; + this.dataFlow = dataFlow; + this.blockEndLocations = blockEndLocations; + this.variables = new Variable[lir.numVariables()]; + this.intervals = new HashMap<>(); + } + + private boolean isAllocatableRegister(CiValue value) { + return isRegister(value) && registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable; + } + + private int curOpId; + private String curUseKind; + + public Interval[] execute() { + ValueProcedure varProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return var(value); } }; + + for (LIRBlock block : lir.linearScanOrder()) { + if (block.phis != null) { + block.phis.forEachOutput(varProc); + } + for (LIRInstruction op : block.lir()) { + op.forEachOutput(varProc); + } + } + + PhiValueProcedure useProc = new PhiValueProcedure() { @Override public CiValue doValue(CiValue value, OperandMode mode, EnumSet flags) { return use(value, mode, flags); } }; + ValueProcedure defProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value, OperandMode mode, EnumSet flags) { return def(value, flags); } }; + + for (int i = lir.linearScanOrder().size() - 1; i >= 0; i--) { + LIRBlock block = lir.linearScanOrder().get(i); + + curOpId = block.lastLirInstructionId() + 2; + for (LIRBlock sux : block.getLIRSuccessors()) { + BitSet suxIn = dataFlow.liveIn(sux); + for (int idx = suxIn.nextSetBit(0); idx >= 0; idx = suxIn.nextSetBit(idx + 1)) { + if (blockEndLocations != null) { + out(blockEndLocations[block.blockID()].get(variables[idx])); + } else { + out(variables[idx]); + } + } + } + + curOpId = block.lastLirInstructionId() + 1; + for (LIRBlock sux : block.getLIRSuccessors()) { + if (sux.phis != null) { + sux.phis.forEachInput(block, useProc); + } + } + + for (int j = block.lir().size() - 1; j >= 0; j--) { + LIRInstruction op = block.lir().get(j); + if (op.id() >= 0) { + curOpId = op.id(); + } else { + curOpId = (curOpId - 1) | 1; + } + + op.forEachOutput(defProc); + op.forEachTemp(defProc); + op.forEachInput(useProc); + op.forEachAlive(useProc); + curUseKind = "L"; + op.forEachState(useProc); + curUseKind = null; + } + + if (block.phis != null) { + curOpId = block.firstLirInstructionId() + 1; + block.phis.forEachOutput(defProc); + } + + for (Interval interval : intervals.values()) { + if (interval.lastTo != 0) { + interval.ranges.add(new Range(block.firstLirInstructionId(), interval.lastTo)); + interval.lastTo = 0; + } + } + } + + Interval[] intervalsArray = intervals.values().toArray(new Interval[0]); + Arrays.sort(intervalsArray, new Comparator() { + @Override + public int compare(Interval o1, Interval o2) { + return o1.orderNum - o2.orderNum; + } + }); + return intervalsArray; + } + + public CiValue var(CiValue value) { + if (isLocation(value)) { + variables[asLocation(value).variable.index] = asLocation(value).variable; + } else if (isVariable(value)) { + variables[asVariable(value).index] = asVariable(value); + } + return value; + } + + private Interval findInterval(CiValue value) { + Interval interval; + if (isLocation(value)) { + Interval parent = findInterval(asLocation(value).variable); + String name = "v" + asLocation(value).variable.index + ":" + asLocation(value).location; + String description = isStackSlot(asLocation(value).location) ? "stack" : ""; + interval = new Interval(asLocation(value).variable.index * 2 + 1001, name, description, parent.name, value.kind.javaName); + + } else if (isVariable(value)) { + interval = new Interval(asVariable(value).index * 2 + 1000, value.toString(), "", value.toString(), value.kind.javaName); + + } else if (isAllocatableRegister(value)) { + interval = new Interval(asRegister(value).number, asRegister(value).toString(), "", asRegister(value).toString(), "fixed"); + + } else { + return null; + } + + Interval existing = intervals.get(interval.name); + if (existing != null) { + return existing; + } + intervals.put(interval.name, interval); + return interval; + } + + private String useKind(EnumSet flags) { + if (curUseKind != null) { + return curUseKind; + } else if (flags.contains(OperandFlag.Stack)) { + return "S"; + } else { + return "M"; + } + } + + private CiValue use(CiValue value, OperandMode mode, EnumSet flags) { + Interval interval = findInterval(value); + if (interval != null) { + if (interval.uses.size() == 0 || interval.uses.get(interval.uses.size() - 1).pos != curOpId) { + interval.uses.add(new UsePosition(curOpId, useKind(flags))); + } + if (interval.lastTo == 0) { + interval.lastTo = curOpId + (mode == OperandMode.Alive ? 1 : 0); + } + } + return value; + } + + private CiValue def(CiValue value, EnumSet flags) { + Interval interval = findInterval(value); + if (interval != null) { + interval.uses.add(new UsePosition(curOpId, useKind(flags))); + if (interval.lastTo == 0) { + interval.ranges.add(new Range(curOpId, curOpId + 1)); + } else { + interval.ranges.add(new Range(curOpId, interval.lastTo)); + } + interval.lastTo = 0; + } + return value; + } + + private CiValue out(CiValue value) { + Interval interval = findInterval(value); + if (interval != null) { + interval.lastTo = curOpId; + } + return value; + } +} diff -r 600cbdce9805 -r 1e3ecb08767d graal/com.oracle.max.graal.printer/src/com/oracle/max/graal/printer/CFGPrinter.java --- a/graal/com.oracle.max.graal.printer/src/com/oracle/max/graal/printer/CFGPrinter.java Wed Jan 18 18:21:52 2012 +0100 +++ b/graal/com.oracle.max.graal.printer/src/com/oracle/max/graal/printer/CFGPrinter.java Wed Jan 18 15:04:03 2012 -0800 @@ -30,6 +30,7 @@ import com.oracle.max.cri.ci.*; import com.oracle.max.cri.ri.*; import com.oracle.max.criutils.*; +import com.oracle.max.graal.alloc.util.*; import com.oracle.max.graal.compiler.alloc.*; import com.oracle.max.graal.compiler.alloc.Interval.UsePosList; import com.oracle.max.graal.compiler.gen.*; @@ -347,6 +348,9 @@ if (block.phis != null) { CiValue[] results = block.phis.results(); for (int i = 0; i < results.length; i++) { + if (i == 0) { + out.printf("nr %4d ", block.firstLirInstructionId()).print(COLUMN_END); + } out.print("instruction PHI ").print(results[i].toString()).print(" = ("); String sep = ""; for (LIRBlock pred : block.getLIRPredecessors()) { @@ -460,4 +464,33 @@ out.printf(" \"%s\"", interval.spillState()); out.println(); } + + public void printIntervals(String label, IntervalPrinter.Interval[] intervals) { + begin("intervals"); + out.println(String.format("name \"%s\"", label)); + + for (IntervalPrinter.Interval interval : intervals) { + printInterval(interval); + } + + end("intervals"); + } + + private void printInterval(IntervalPrinter.Interval interval) { + out.printf("%s %s \"%s\" %s %s ", interval.name, interval.type, interval.description, interval.variable, "no"); + if (interval.ranges.size() == 0) { + // One range is required in the spec, so output a dummy range. + out.printf("[0, 0[ "); + } else { + for (IntervalPrinter.Range range : interval.ranges) { + out.printf("[%d, %d[ ", range.from, range.to); + } + } + for (IntervalPrinter.UsePosition usePos : interval.uses) { + out.printf("%d %s ", usePos.pos, usePos.kind); + } + out.printf("\"%s\"", "no"); + out.println(); + } } + diff -r 600cbdce9805 -r 1e3ecb08767d graal/com.oracle.max.graal.printer/src/com/oracle/max/graal/printer/CFGPrinterObserver.java --- a/graal/com.oracle.max.graal.printer/src/com/oracle/max/graal/printer/CFGPrinterObserver.java Wed Jan 18 18:21:52 2012 +0100 +++ b/graal/com.oracle.max.graal.printer/src/com/oracle/max/graal/printer/CFGPrinterObserver.java Wed Jan 18 15:04:03 2012 -0800 @@ -28,6 +28,7 @@ import com.oracle.max.cri.ci.*; import com.oracle.max.cri.ri.*; import com.oracle.max.criutils.*; +import com.oracle.max.graal.alloc.util.*; import com.oracle.max.graal.compiler.alloc.*; import com.oracle.max.graal.compiler.gen.*; import com.oracle.max.graal.compiler.lir.*; @@ -89,6 +90,7 @@ IdentifyBlocksPhase schedule = event.debugObject(IdentifyBlocksPhase.class); LinearScan allocator = event.debugObject(LinearScan.class); Interval[] intervals = event.debugObject(Interval[].class); + IntervalPrinter.Interval[] printIntervals = event.debugObject(IntervalPrinter.Interval[].class); CiTargetMethod targetMethod = event.debugObject(CiTargetMethod.class); if (blockMap != null) { @@ -121,6 +123,9 @@ if (allocator != null && intervals != null) { cfgPrinter.printIntervals(event.label, intervals); } + if (printIntervals != null) { + cfgPrinter.printIntervals(event.label, printIntervals); + } } @Override