Mercurial > hg > truffle

changeset 4295:1e3ecb08767d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Output of lifetime intervals for new register allocator
author Christian Wimmer <Christian.Wimmer@Oracle.com>
date Wed, 18 Jan 2012 15:04:03 -0800
parents 600cbdce9805
children d089b71a5237 874fcc2ddd9d
files graal/com.oracle.max.cri/src/com/oracle/max/cri/ci/CiStackSlot.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/DataFlowAnalysis.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/LinearScanAllocator.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/SpillAllAllocator.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/IntervalPrinter.java graal/com.oracle.max.graal.printer/src/com/oracle/max/graal/printer/CFGPrinter.java graal/com.oracle.max.graal.printer/src/com/oracle/max/graal/printer/CFGPrinterObserver.java
diffstat 7 files changed, 330 insertions(+), 13 deletions(-) [+]
line wrap: on
line diff
--- 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();
         }
     }
 
--- 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();
     }
 
--- 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);
--- 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);
--- /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<Range> ranges;
+        public final List<UsePosition> 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<String, Interval> 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<OperandFlag> flags) { return use(value, mode, flags); } };
+        ValueProcedure    defProc = new ValueProcedure() {    @Override public CiValue doValue(CiValue value, OperandMode mode, EnumSet<OperandFlag> 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<Interval>() {
+            @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<OperandFlag> 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<OperandFlag> 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<OperandFlag> 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;
+    }
+}
--- 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();
+    }
 }
+
--- 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