# HG changeset patch # User Gilles Duboscq # Date 1310674964 -7200 # Node ID 034a4db85c59afc70e88977d9a0ac911d5292413 # Parent 0ab38d1437957678f5d3d9cdb3a004d7b9211d31 Draft rematerialization after eager GVN, only canonicalize new nodes after loop optimisations diff -r 0ab38d143795 -r 034a4db85c59 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalMetrics.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalMetrics.java Wed Jul 13 15:08:49 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalMetrics.java Thu Jul 14 22:22:44 2011 +0200 @@ -64,6 +64,10 @@ public static int NodesCanonicalized; public static int LoopsPeeled; public static int LoopsInverted; + public static int PartialUsageProbability; + public static int FullUsageProbability; + public static int Rematerializations; + public static int GlobalValueNumberingHits; public static void print() { for (Entry m : map.entrySet()) { diff -r 0ab38d143795 -r 034a4db85c59 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Wed Jul 13 15:08:49 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Thu Jul 14 22:22:44 2011 +0200 @@ -63,6 +63,9 @@ // absolute probability analysis public static boolean ProbabilityAnalysis = true; + //rematerialize settings + public static double MinimumUsageProbability = 0.95; + // debugging settings public static boolean VerifyPointerMaps = ____; public static int MethodEndBreakpointGuards = 0; @@ -161,6 +164,7 @@ public static boolean OptReadElimination = ____; public static boolean OptGVN = ____; + public static boolean Rematerialize = ____; public static boolean OptCanonicalizer = true; public static boolean OptLoops = ____; public static boolean OptOptimisticSchedule = ____; diff -r 0ab38d143795 -r 034a4db85c59 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Wed Jul 13 15:08:49 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Thu Jul 14 22:22:44 2011 +0200 @@ -111,9 +111,10 @@ } if (GraalOptions.OptLoops) { + graph.mark(); new LoopPhase().apply(graph); if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase().apply(graph); + new CanonicalizerPhase(true).apply(graph); new DeadCodeEliminationPhase().apply(graph); } } @@ -126,6 +127,9 @@ if (GraalOptions.OptGVN) { new GlobalValueNumberingPhase().apply(graph); + if (GraalOptions.Rematerialize) { + new RematerializationPhase().apply(graph); + } } new LoweringPhase(compilation.runtime).apply(graph); @@ -133,6 +137,9 @@ new MemoryPhase().apply(graph); if (GraalOptions.OptGVN) { new GlobalValueNumberingPhase().apply(graph); + if (GraalOptions.Rematerialize) { + new RematerializationPhase().apply(graph); + } } if (GraalOptions.OptReadElimination) { new ReadEliminationPhase().apply(graph); diff -r 0ab38d143795 -r 034a4db85c59 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java Wed Jul 13 15:08:49 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java Thu Jul 14 22:22:44 2011 +0200 @@ -25,17 +25,25 @@ import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.graph.*; -/* TODO (gd) Canonicalize : - * - Compare & If - * - InstanceOf (if it's not transformed into a Condition for Compare) - * - Switches - */ public class CanonicalizerPhase extends Phase { private static final int MAX_ITERATION_PER_NODE = 10; + private boolean newNodes; + + public CanonicalizerPhase() { + this(false); + } + + public CanonicalizerPhase(boolean newNodes) { + this.newNodes = newNodes; + } + @Override protected void run(Graph graph) { - NodeWorkList nodeWorkList = graph.createNodeWorkList(true, MAX_ITERATION_PER_NODE); + NodeWorkList nodeWorkList = graph.createNodeWorkList(!newNodes, MAX_ITERATION_PER_NODE); + if (newNodes) { + nodeWorkList.addAll(graph.getNewNodes()); + } for (Node node : nodeWorkList) { CanonicalizerOp op = node.lookup(CanonicalizerOp.class); if (op != null) { diff -r 0ab38d143795 -r 034a4db85c59 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GlobalValueNumberingPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GlobalValueNumberingPhase.java Wed Jul 13 15:08:49 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GlobalValueNumberingPhase.java Thu Jul 14 22:22:44 2011 +0200 @@ -46,8 +46,11 @@ apply(input, visited); } Node newNode = n.graph().ideal(n); - if (GraalOptions.TraceGVN && newNode != n) { - TTY.println("GVN applied and new node is " + newNode); + if (newNode != n) { + GraalMetrics.GlobalValueNumberingHits++; + if (GraalOptions.TraceGVN) { + TTY.println("GVN applied and new node is " + newNode); + } } } } diff -r 0ab38d143795 -r 034a4db85c59 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/RematerializationPhase.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/RematerializationPhase.java Thu Jul 14 22:22:44 2011 +0200 @@ -0,0 +1,246 @@ +/* + * Copyright (c) 2011, 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.compiler.phases; + +import java.text.*; +import java.util.*; + +import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.schedule.*; +import com.oracle.max.graal.compiler.util.*; +import com.oracle.max.graal.graph.*; + + +public class RematerializationPhase extends Phase { + + private NodeMap nodeToBlock; + private HashMap newNodesToBlock; + private List blocks; + private UsageProbability[] probablityCache; + private boolean ignoreUsages; + + @Override + protected void run(Graph graph) { + final IdentifyBlocksPhase s = new IdentifyBlocksPhase(true); + s.apply(graph); + + newNodesToBlock = new HashMap(); + nodeToBlock = s.getNodeToBlock(); + blocks = s.getBlocks(); + + probablityCache = new UsageProbability[blocks.size()]; + + NodeWorkList work = graph.createNodeWorkList(); + NodeBitMap done = graph.createNodeBitMap(); + work.addAll(graph.getNodes(FloatingNode.class)); + + for (Node node : work) { + if (node instanceof Phi || node instanceof Local || node instanceof Constant || node instanceof LocationNode) { + done.mark(node); + continue; + } + boolean delay = false; + for (Node usage : node.usages()) { + if (usage instanceof FloatingNode && !(usage instanceof Phi) && done.isNotNewNotMarked(usage)) { + delay = true; + break; + } + } + if (delay) { + work.addAgain(node); + continue; + } + done.mark(node); + Arrays.fill(probablityCache, null); + ignoreUsages = true; + Block block = nodeToBlock.get(node); + if (block == null) { + continue; + } + UsageProbability usageProbability = usageProbability(node, block); + if (usageProbability.probability < GraalOptions.MinimumUsageProbability) { + if (ignoreUsages) { + ignoreUsages = false; + Arrays.fill(probablityCache, null); + usageProbability = usageProbability(node, block); // recompute with usage maps + } + //System.out.println("going to remarterialize " + node + " at " + block + " : " + toString(usageProbability)); + boolean first = true; + for (Block sux : block.getSuccessors()) { + if (first) { + first = false; + continue; + } + usageProbability = usageProbability(node, sux); + List usages = new LinkedList(); + for (Node usage : usageProbability.usages) { + usages.add(usage); + } + if (!usages.isEmpty()) { + Node copy = node.copyWithEdges(); + newNodesToBlock.put(copy, sux); + GraalMetrics.Rematerializations++; + //System.out.println("Rematerialized " + node + " : " + toString(usageProbability)); + for (Node usage : usages) { + usage.inputs().replace(node, copy); + } + } + } + } + } + } + + private UsageProbability usageProbability(Node n, Block b) { + UsageProbability cached = probablityCache[b.blockID()]; + if (cached != null) { + return cached; + } + if (ignoreUsages) { + GraalMetrics.PartialUsageProbability++; + } else { + GraalMetrics.FullUsageProbability++; + } + for (Node usage : n.usages()) { + if (usage instanceof Phi) { + Phi phi = (Phi) usage; + Merge merge = phi.merge(); + for (int i = 0; i < phi.valueCount(); i++) { + if (phi.valueAt(i) == n) { + insertUsageInCache(merge.phiPredecessorAt(i)); + } + } + } else { + insertUsageInCache(usage); + } + } + return usageProbability0(n, b); + } + + private void insertUsageInCache(Node usage) { + Block block = block(usage); + if (block == null) { + return; + } + int blockID = block.blockID(); + UsageProbability usageProbability = probablityCache[blockID]; + if (usageProbability == null) { + probablityCache[blockID] = new UsageProbability(usage); + } else if (!ignoreUsages) { + usageProbability.usages.mark(usage); + } + } + + private Block block(Node node) { + Block block; + if (!nodeToBlock.isNew(node)) { + block = nodeToBlock.get(node); + } else { + block = newNodesToBlock.get(node); + assert block != null; + } + return block; + } + + private UsageProbability usageProbability0(Node n, Block b) { + //System.out.println("usageProbability0(" + n.id() + ", " + b + ")"); + UsageProbability cached = probablityCache[b.blockID()]; + if (cached != null && (cached.computed || ignoreUsages)) { + return cached; + } + UsageProbability result = cached; + if (result == null) { + result = new UsageProbability(n.graph()); + } + if (b.getSuccessors().size() > 0) { + if (b.isLoopEnd()) { + Block loopHeader = b.getSuccessors().get(0); + assert loopHeader.isLoopHeader(); + UsageProbability headerUsages = probablityCache[loopHeader.blockID()]; + if (headerUsages != null) { + result.merge(headerUsages, 1.0); + } + } else if (b.getSuccessors().size() == 1) { + result.merge(usageProbability0(n, b.getSuccessors().get(0)), 1.0); + } else { + Node lastNode = b.lastNode(); + if (lastNode instanceof Invoke) { + result.merge(usageProbability0(n, nodeToBlock.get(((Invoke) lastNode).next())), 1.0); + result.merge(usageProbability0(n, nodeToBlock.get(((Invoke) lastNode).exceptionEdge())), 0.0); + } else if (lastNode instanceof ControlSplit) { + ControlSplit split = (ControlSplit) lastNode; + for (int i = 0; i < split.blockSuccessorCount(); i++) { + result.merge(usageProbability0(n, nodeToBlock.get(split.blockSuccessor(i))), split.probability(i)); + } + } else { + throw Util.shouldNotReachHere(); + } + } + } + probablityCache[b.blockID()] = result; + result.computed = true; + return result; + } + + private class UsageProbability { + double probability; + NodeBitMap usages; + boolean computed; + + public UsageProbability(Node usage) { + if (!ignoreUsages) { + usages = usage.graph().createNodeBitMap(); + usages.mark(usage); + } + probability = 1.0; + } + + public UsageProbability(Graph graph) { + if (!ignoreUsages) { + usages = graph.createNodeBitMap(); + } + probability = 0.0; + } + + public void merge(UsageProbability sux, double suxProbability) { + if (!ignoreUsages) { + usages.setUnion(sux.usages); + } + probability += suxProbability * sux.probability; + } + } + + private String toString(UsageProbability up) { + NumberFormat nf = NumberFormat.getPercentInstance(); + StringBuilder sb = new StringBuilder("p="); + sb.append(nf.format(up.probability)); + sb.append(" U=["); + for (Node n : up.usages) { + sb.append(n); + sb.append(", "); + } + sb.append("]"); + return sb.toString(); + } +} +