Mercurial > hg > graal-compiler
view graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/FloatingReadPhase.java @ 5449:56f4afcf71f7
Merge
author | Gilles Duboscq <duboscq@ssw.jku.at> |
---|---|
date | Fri, 25 May 2012 13:22:45 +0200 |
parents | 0368c19fc175 645534f5e4ab |
children | 380b2a73fdc2 |
line wrap: on
line source
/* * 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.graal.compiler.phases; import java.util.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.PhiNode.PhiType; import com.oracle.graal.nodes.extended.*; public class FloatingReadPhase extends Phase { private static class MemoryMap { private Block block; private IdentityHashMap<Object, Node> map; private IdentityHashMap<Object, Node> loopEntryMap; private int mergeOperationCount; public MemoryMap(Block block) { this.block = block; map = new IdentityHashMap<>(); } public MemoryMap(Block block, MemoryMap other) { this(block); map.putAll(other.map); } public void mergeLoopEntryWith(MemoryMap otherMemoryMap, LoopBeginNode begin, EndNode pred) { for (Object keyInOther : otherMemoryMap.map.keySet()) { assert loopEntryMap.containsKey(keyInOther) || map.get(keyInOther) == otherMemoryMap.map.get(keyInOther) : keyInOther + ", " + map.get(keyInOther) + " vs " + otherMemoryMap.map.get(keyInOther) + " " + begin; } for (Map.Entry<Object, Node> entry : loopEntryMap.entrySet()) { PhiNode phiNode = (PhiNode) entry.getValue(); Object key = entry.getKey(); Node other; if (otherMemoryMap.map.containsKey(key)) { other = otherMemoryMap.map.get(key); } else { other = otherMemoryMap.map.get(LocationNode.ANY_LOCATION); } // this explicitly honors the phi input index, since the iteration order will not always adhere to the end index ordering. // TODO(ls) check for instances of this problem in other places. int index = begin.phiPredecessorIndex(pred); phiNode.initializeValueAt(index, (ValueNode) other); } } public void mergeWith(MemoryMap otherMemoryMap, Block b) { Debug.log("Merging block %s into block %s.", otherMemoryMap.block, block); IdentityHashMap<Object, Node> otherMap = otherMemoryMap.map; for (Map.Entry<Object, Node> entry : map.entrySet()) { if (otherMap.containsKey(entry.getKey())) { mergeNodes(entry.getKey(), entry.getValue(), otherMap.get(entry.getKey()), b); } else { mergeNodes(entry.getKey(), entry.getValue(), otherMap.get(LocationNode.ANY_LOCATION), b); } } Node anyLocationNode = map.get(LocationNode.ANY_LOCATION); for (Map.Entry<Object, Node> entry : otherMap.entrySet()) { if (!map.containsKey(entry.getKey())) { Node current = anyLocationNode; if (anyLocationNode instanceof PhiNode) { PhiNode phiNode = (PhiNode) anyLocationNode; if (phiNode.merge() == block.getBeginNode()) { PhiNode phiCopy = (PhiNode) phiNode.copyWithInputs(); phiCopy.removeInput(phiCopy.valueCount() - 1); current = phiCopy; map.put(entry.getKey(), current); } } mergeNodes(entry.getKey(), current, entry.getValue(), b); } } mergeOperationCount++; } private void mergeNodes(Object location, Node original, Node newValue, Block mergeBlock) { if (original == newValue) { Debug.log("Nothing to merge both nodes are %s.", original); return; } MergeNode m = (MergeNode) mergeBlock.getBeginNode(); if (m.isPhiAtMerge(original)) { PhiNode phi = (PhiNode) original; phi.addInput((ValueNode) newValue); Debug.log("Add new input to %s: %s.", original, newValue); assert phi.valueCount() <= phi.merge().forwardEndCount() : phi.merge(); } else { PhiNode phi = m.graph().unique(new PhiNode(PhiType.Memory, m)); // TODO(ls) how does this work? add documentation ... for (int i = 0; i < mergeOperationCount + 1; ++i) { phi.addInput((ValueNode) original); } phi.addInput((ValueNode) newValue); Debug.log("Creating new %s merge=%s newValue=%s location=%s.", phi, phi.merge(), newValue, location); assert phi.valueCount() <= phi.merge().forwardEndCount() + ((phi.merge() instanceof LoopBeginNode) ? 1 : 0) : phi.merge() + "/" + phi.valueCount() + "/" + phi.merge().forwardEndCount() + "/" + mergeOperationCount; assert m.usages().contains(phi); assert phi.merge().usages().contains(phi); for (Node input : phi.inputs()) { assert input.usages().contains(phi); } map.put(location, phi); } } public void processCheckpoint(MemoryCheckpoint checkpoint) { map.clear(); map.put(LocationNode.ANY_LOCATION, (Node) checkpoint); } public void processWrite(WriteNode writeNode) { map.put(writeNode.location().locationIdentity(), writeNode); } public void processRead(ReadNode readNode) { StructuredGraph graph = (StructuredGraph) readNode.graph(); assert readNode.getNullCheck() == false; Debug.log("Register read to node %s.", readNode); FloatingReadNode floatingRead; if (readNode.location().locationIdentity() == LocationNode.FINAL_LOCATION) { floatingRead = graph.unique(new FloatingReadNode(readNode.object(), readNode.location(), null, readNode.stamp(), readNode.dependencies())); } else { floatingRead = graph.unique(new FloatingReadNode(readNode.object(), readNode.location(), getLocationForRead(readNode), readNode.stamp(), readNode.dependencies())); } floatingRead.setNullCheck(readNode.getNullCheck()); ValueAnchorNode anchor = null; for (GuardNode guard : readNode.dependencies().filter(GuardNode.class)) { if (anchor == null) { anchor = graph.add(new ValueAnchorNode()); } anchor.addAnchoredNode(guard); } if (anchor != null) { graph.addAfterFixed(readNode, anchor); } graph.replaceFixedWithFloating(readNode, floatingRead); } private Node getLocationForRead(ReadNode readNode) { Object locationIdentity = readNode.location().locationIdentity(); Node result = map.get(locationIdentity); if (result == null) { result = map.get(LocationNode.ANY_LOCATION); } return result; } public void createLoopEntryMemoryMap(Set<Object> modifiedLocations, Loop loop) { loopEntryMap = new IdentityHashMap<>(); for (Object modifiedLocation : modifiedLocations) { Node other; if (map.containsKey(modifiedLocation)) { other = map.get(modifiedLocation); } else { other = map.get(LocationNode.ANY_LOCATION); } createLoopEntryPhi(modifiedLocation, other, loop); } if (modifiedLocations.contains(LocationNode.ANY_LOCATION)) { for (Map.Entry<Object, Node> entry : map.entrySet()) { if (!modifiedLocations.contains(entry.getKey())) { createLoopEntryPhi(entry.getKey(), entry.getValue(), loop); } } } } private void createLoopEntryPhi(Object modifiedLocation, Node other, Loop loop) { PhiNode phi = other.graph().unique(new PhiNode(PhiType.Memory, (MergeNode) loop.header.getBeginNode())); phi.addInput((ValueNode) other); map.put(modifiedLocation, phi); loopEntryMap.put(modifiedLocation, phi); } public IdentityHashMap<Object, Node> getLoopEntryMap() { return loopEntryMap; } } @Override protected void run(StructuredGraph graph) { // Add start node write checkpoint. addStartCheckpoint(graph); // Identify blocks. ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); Block[] blocks = cfg.getBlocks(); HashMap<Loop, Set<Object>> modifiedValues = new HashMap<>(); // Initialize modified values to empty hash set. for (Loop loop : cfg.getLoops()) { modifiedValues.put(loop, new HashSet<>()); } // Get modified values in loops. for (Node n : graph.getNodes()) { Block block = cfg.blockFor(n); if (block != null && block.getLoop() != null) { if (n instanceof WriteNode) { WriteNode writeNode = (WriteNode) n; traceWrite(block.getLoop(), writeNode.location().locationIdentity(), modifiedValues); } else if (n instanceof MemoryCheckpoint) { traceMemoryCheckpoint(block.getLoop(), modifiedValues); } } } // Propagate values to parent loops. for (Loop loop : cfg.getLoops()) { if (loop.depth == 1) { propagateFromChildren(loop, modifiedValues); } } Debug.log("Modified values: %s.", modifiedValues); // Process blocks (predecessors first). MemoryMap[] memoryMaps = new MemoryMap[blocks.length]; for (final Block b : blocks) { processBlock(b, memoryMaps, cfg.getNodeToBlock(), modifiedValues); } } private static void addStartCheckpoint(StructuredGraph graph) { BeginNode entryPoint = graph.start(); FixedNode next = entryPoint.next(); if (!(next instanceof MemoryCheckpoint)) { graph.addAfterFixed(entryPoint, graph.add(new WriteMemoryCheckpointNode())); } } private static void processBlock(Block b, MemoryMap[] memoryMaps, NodeMap<Block> nodeToBlock, HashMap<Loop, Set<Object>> modifiedValues) { // Create initial memory map for the block. MemoryMap map = null; if (b.getPredecessors().size() == 0) { map = new MemoryMap(b); } else { map = new MemoryMap(b, memoryMaps[b.getPredecessors().get(0).getId()]); if (b.isLoopHeader()) { Loop loop = b.getLoop(); map.createLoopEntryMemoryMap(modifiedValues.get(loop), loop); } for (int i = 1; i < b.getPredecessors().size(); ++i) { Block block = b.getPredecessors().get(i); if (!block.isLoopEnd()) { map.mergeWith(memoryMaps[block.getId()], b); } } } memoryMaps[b.getId()] = map; // Process instructions of this block. for (Node n : b.getNodes()) { if (n instanceof ReadNode) { ReadNode readNode = (ReadNode) n; map.processRead(readNode); } else if (n instanceof WriteNode) { WriteNode writeNode = (WriteNode) n; map.processWrite(writeNode); } else if (n instanceof MemoryCheckpoint) { MemoryCheckpoint checkpoint = (MemoryCheckpoint) n; map.processCheckpoint(checkpoint); } } if (b.getEndNode() instanceof LoopEndNode) { LoopEndNode end = (LoopEndNode) b.getEndNode(); LoopBeginNode begin = end.loopBegin(); Block beginBlock = nodeToBlock.get(begin); MemoryMap memoryMap = memoryMaps[beginBlock.getId()]; assert memoryMap != null; assert memoryMap.getLoopEntryMap() != null; memoryMap.mergeLoopEntryWith(map, begin, (EndNode) b.getEndNode()); } } private static void traceMemoryCheckpoint(Loop loop, HashMap<Loop, Set<Object>> modifiedValues) { modifiedValues.get(loop).add(LocationNode.ANY_LOCATION); } private void propagateFromChildren(Loop loop, HashMap<Loop, Set<Object>> modifiedValues) { for (Loop child : loop.children) { propagateFromChildren(child, modifiedValues); modifiedValues.get(loop).addAll(modifiedValues.get(child)); } } private static void traceWrite(Loop loop, Object locationIdentity, HashMap<Loop, Set<Object>> modifiedValues) { modifiedValues.get(loop).add(locationIdentity); } }