Mercurial > hg > graal-compiler
view graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java @ 16515:d6ac7470603e
Merge with b0ea5c266655253934e403f00d69aedc1f68e052
author | Michael Van De Vanter <michael.van.de.vanter@oracle.com> |
---|---|
date | Tue, 15 Jul 2014 14:23:31 -0700 |
parents | a039ae7e0e50 |
children | ca2b422e8f50 |
line wrap: on
line source
/* * 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.graal.loop; import java.util.*; import com.oracle.graal.compiler.common.*; import com.oracle.graal.graph.*; import com.oracle.graal.graph.Graph.DuplicationReplacement; import com.oracle.graal.graph.iterators.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.virtual.*; public abstract class LoopFragment { private final LoopEx loop; private final LoopFragment original; protected NodeBitMap nodes; protected boolean nodesReady; private Map<Node, Node> duplicationMap; public LoopFragment(LoopEx loop) { this(loop, null); this.nodesReady = true; } public LoopFragment(LoopEx loop, LoopFragment original) { this.loop = loop; this.original = original; this.nodesReady = false; } public LoopEx loop() { return loop; } public abstract LoopFragment duplicate(); public abstract void insertBefore(LoopEx l); public void disconnect() { // TODO (gd) possibly abstract } public boolean contains(Node n) { return nodes().isMarkedAndGrow(n); } @SuppressWarnings("unchecked") public <New extends Node, Old extends New> New getDuplicatedNode(Old n) { assert isDuplicate(); return (New) duplicationMap.get(n); } protected <New extends Node, Old extends New> void putDuplicatedNode(Old oldNode, New newNode) { duplicationMap.put(oldNode, newNode); } /** * Gets the corresponding value in this fragment. Should be called on duplicate fragments with a * node from the original fragment as argument. * * @param b original value * @return corresponding value in the peel */ protected abstract ValueNode prim(ValueNode b); public boolean isDuplicate() { return original != null; } public LoopFragment original() { return original; } public abstract NodeBitMap nodes(); public StructuredGraph graph() { LoopEx l; if (isDuplicate()) { l = original().loop(); } else { l = loop(); } return l.loopBegin().graph(); } protected abstract DuplicationReplacement getDuplicationReplacement(); protected abstract void finishDuplication(); protected void patchNodes(final DuplicationReplacement dataFix) { if (isDuplicate() && !nodesReady) { assert !original.isDuplicate(); final DuplicationReplacement cfgFix = original().getDuplicationReplacement(); DuplicationReplacement dr; if (cfgFix == null && dataFix != null) { dr = dataFix; } else if (cfgFix != null && dataFix == null) { dr = cfgFix; } else if (cfgFix != null && dataFix != null) { dr = new DuplicationReplacement() { @Override public Node replacement(Node o) { Node r1 = dataFix.replacement(o); if (r1 != o) { assert cfgFix.replacement(o) == o; return r1; } Node r2 = cfgFix.replacement(o); if (r2 != o) { return r2; } return o; } }; } else { dr = null; } NodeIterable<Node> nodesIterable = original().nodes(); duplicationMap = graph().addDuplicates(nodesIterable, graph(), nodesIterable.count(), dr); finishDuplication(); nodesReady = true; } else { // TODO (gd) apply fix ? } } protected static NodeBitMap computeNodes(Graph graph, Iterable<BeginNode> blocks) { return computeNodes(graph, blocks, Collections.emptyList()); } protected static NodeBitMap computeNodes(Graph graph, Iterable<BeginNode> blocks, Iterable<LoopExitNode> earlyExits) { final NodeBitMap nodes = graph.createNodeBitMap(); for (BeginNode b : blocks) { if (b.isDeleted()) { continue; } for (Node n : b.getBlockNodes()) { if (n instanceof Invoke) { nodes.mark(((Invoke) n).callTarget()); } if (n instanceof NodeWithState) { NodeWithState withState = (NodeWithState) n; withState.states().forEach(state -> state.applyToVirtual(node -> nodes.mark(node))); } nodes.mark(n); } } for (LoopExitNode earlyExit : earlyExits) { if (earlyExit.isDeleted()) { continue; } FrameState stateAfter = earlyExit.stateAfter(); if (stateAfter != null) { stateAfter.applyToVirtual(node -> nodes.mark(node)); } nodes.mark(earlyExit); for (ProxyNode proxy : earlyExit.proxies()) { nodes.mark(proxy); } } final NodeBitMap notloopNodes = graph.createNodeBitMap(); for (BeginNode b : blocks) { if (b.isDeleted()) { continue; } for (Node n : b.getBlockNodes()) { if (n instanceof CommitAllocationNode) { for (VirtualObjectNode obj : ((CommitAllocationNode) n).getVirtualObjects()) { markFloating(obj, nodes, notloopNodes); } } if (n instanceof MonitorEnterNode) { markFloating(((MonitorEnterNode) n).getMonitorId(), nodes, notloopNodes); } for (Node usage : n.usages()) { markFloating(usage, nodes, notloopNodes); } } } return nodes; } private static boolean markFloating(Node n, NodeBitMap loopNodes, NodeBitMap notloopNodes) { if (loopNodes.isMarked(n)) { return true; } if (notloopNodes.isMarked(n)) { return false; } if (n instanceof FixedNode) { return false; } boolean mark = false; if (n instanceof PhiNode) { PhiNode phi = (PhiNode) n; mark = loopNodes.isMarked(phi.merge()); if (mark) { loopNodes.mark(n); } else { notloopNodes.mark(n); return false; } } for (Node usage : n.usages()) { if (markFloating(usage, loopNodes, notloopNodes)) { mark = true; } } if (mark) { loopNodes.mark(n); return true; } notloopNodes.mark(n); return false; } public static NodeIterable<BeginNode> toHirBlocks(final Iterable<Block> blocks) { return new NodeIterable<BeginNode>() { public Iterator<BeginNode> iterator() { final Iterator<Block> it = blocks.iterator(); return new Iterator<BeginNode>() { @Override public void remove() { throw new UnsupportedOperationException(); } public BeginNode next() { return it.next().getBeginNode(); } public boolean hasNext() { return it.hasNext(); } }; } }; } public static NodeIterable<LoopExitNode> toHirExits(final Iterable<Block> blocks) { return new NodeIterable<LoopExitNode>() { public Iterator<LoopExitNode> iterator() { final Iterator<Block> it = blocks.iterator(); return new Iterator<LoopExitNode>() { @Override public void remove() { throw new UnsupportedOperationException(); } public LoopExitNode next() { return (LoopExitNode) it.next().getBeginNode(); } public boolean hasNext() { return it.hasNext(); } }; } }; } /** * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with * the original fragment's exits. */ protected void mergeEarlyExits() { assert isDuplicate(); StructuredGraph graph = graph(); for (BeginNode earlyExit : LoopFragment.toHirBlocks(original().loop().loop().getExits())) { LoopExitNode loopEarlyExit = (LoopExitNode) earlyExit; FixedNode next = loopEarlyExit.next(); if (loopEarlyExit.isDeleted() || !this.original().contains(loopEarlyExit)) { continue; } BeginNode newEarlyExit = getDuplicatedNode(loopEarlyExit); if (newEarlyExit == null) { continue; } MergeNode merge = graph.add(new MergeNode()); AbstractEndNode originalEnd = graph.add(new EndNode()); AbstractEndNode newEnd = graph.add(new EndNode()); merge.addForwardEnd(originalEnd); merge.addForwardEnd(newEnd); loopEarlyExit.setNext(originalEnd); newEarlyExit.setNext(newEnd); merge.setNext(next); FrameState exitState = loopEarlyExit.stateAfter(); if (exitState != null) { FrameState originalExitState = exitState; exitState = exitState.duplicateWithVirtualState(); loopEarlyExit.setStateAfter(exitState); merge.setStateAfter(originalExitState); /* * Using the old exit's state as the merge's state is necessary because some of the * VirtualState nodes contained in the old exit's state may be shared by other * dominated VirtualStates. Those dominated virtual states need to see the * proxy->phi update that are applied below. * * We now update the original fragment's nodes accordingly: */ originalExitState.applyToVirtual(node -> original.nodes.clearAndGrow(node)); exitState.applyToVirtual(node -> original.nodes.markAndGrow(node)); } FrameState finalExitState = exitState; for (Node anchored : loopEarlyExit.anchored().snapshot()) { anchored.replaceFirstInput(loopEarlyExit, merge); } boolean newEarlyExitIsLoopExit = newEarlyExit instanceof LoopExitNode; for (final ProxyNode vpn : loopEarlyExit.proxies().snapshot()) { if (vpn.usages().isEmpty()) { continue; } final ValueNode replaceWith; ValueNode newVpn = prim(newEarlyExitIsLoopExit ? vpn : vpn.value()); if (newVpn != null) { PhiNode phi; if (vpn instanceof ValueProxyNode) { phi = graph.addWithoutUnique(new ValuePhiNode(vpn.stamp(), merge)); } else if (vpn instanceof GuardProxyNode) { phi = graph.addWithoutUnique(new GuardPhiNode(merge)); } else { throw GraalInternalError.shouldNotReachHere(); } phi.addInput(vpn); phi.addInput(newVpn); replaceWith = phi; } else { replaceWith = vpn.value(); } vpn.replaceAtMatchingUsages(replaceWith, usage -> { if (merge.isPhiAtMerge(usage)) { return false; } if (usage instanceof VirtualState) { VirtualState stateUsage = (VirtualState) usage; if (finalExitState.isPartOfThisState(stateUsage)) { return false; } } return true; }); } } } }