Mercurial > hg > truffle
view graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/FloatingReadPhase.java @ 4199:aaac4894175c
Renamed cri packages from sun to oracle.
author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
---|---|
date | Tue, 03 Jan 2012 16:29:28 +0100 |
parents | bc8527f3071c |
children | 1aaf3592e516 |
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.max.graal.compiler.phases; import java.util.*; import com.oracle.max.cri.ci.*; import com.oracle.max.criutils.*; import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.loop.*; import com.oracle.max.graal.compiler.schedule.*; import com.oracle.max.graal.graph.*; import com.oracle.max.graal.nodes.*; import com.oracle.max.graal.nodes.PhiNode.*; import com.oracle.max.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) { 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(); assert phiNode.valueCount() == 1; Node other; Object key = entry.getKey(); if (otherMemoryMap.map.containsKey(key)) { other = otherMemoryMap.map.get(key); } else { other = otherMemoryMap.map.get(LocationNode.ANY_LOCATION); } phiNode.addInput((ValueNode) other); } } public void mergeWith(MemoryMap otherMemoryMap, Block b) { if (GraalOptions.TraceMemoryMaps) { TTY.println("merging block " + otherMemoryMap.block + " into 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.firstNode()) { 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) { // Nothing to merge. if (GraalOptions.TraceMemoryMaps) { TTY.println("Nothing to merge both nodes are " + original); } return; } MergeNode m = (MergeNode) mergeBlock.firstNode(); if (m.isPhiAtMerge(original)) { PhiNode phi = (PhiNode) original; phi.addInput((ValueNode) newValue); if (GraalOptions.TraceMemoryMaps) { TTY.println("Add new input to " + original + ": " + newValue); } assert phi.valueCount() <= phi.merge().endCount() : phi.merge(); } else { assert m != null; PhiNode phi = m.graph().unique(new PhiNode(CiKind.Illegal, m, PhiType.Memory)); for (int i = 0; i < mergeOperationCount + 1; ++i) { phi.addInput((ValueNode) original); } phi.addInput((ValueNode) newValue); if (GraalOptions.TraceMemoryMaps) { TTY.println("Creating new " + phi + " merge=" + phi.merge() + ", mergeOperationCount=" + mergeOperationCount + ", newValue=" + newValue + ", location=" + location); } assert phi.valueCount() <= phi.merge().endCount() + ((phi.merge() instanceof LoopBeginNode) ? 1 : 0) : phi.merge() + "/" + phi.valueCount() + "/" + phi.merge().endCount() + "/" + 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) { FixedNode next = readNode.next(); readNode.setNext(null); readNode.replaceAtPredecessors(next); if (GraalOptions.TraceMemoryMaps) { TTY.println("Register read to node " + readNode); } if (readNode.location().locationIdentity() != LocationNode.FINAL_LOCATION) { // Create dependency on previous node that creates the memory state for this location. readNode.addDependency(getLocationForRead(readNode)); } } 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(CiKind.Illegal, loop.loopBegin(), PhiType.Memory)); 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); LoopInfo loopInfo = LoopUtil.computeLoopInfo(graph); HashMap<Loop, Set<Object>> modifiedValues = new HashMap<>(); // Initialize modified values to empty hash set. for (Loop loop : loopInfo.loops()) { modifiedValues.put(loop, new HashSet<>()); } // Get modified values in loops. for (Node n : graph.getNodes()) { Loop loop = loopInfo.loop(n); if (loop != null) { if (n instanceof WriteNode) { WriteNode writeNode = (WriteNode) n; traceWrite(loop, writeNode.location().locationIdentity(), modifiedValues); } else if (n instanceof MemoryCheckpoint) { traceMemoryCheckpoint(loop, modifiedValues); } } } // Propagate values to parent loops. for (Loop loop : loopInfo.rootLoops()) { propagateFromChildren(loop, modifiedValues); } if (GraalOptions.TraceMemoryMaps) { print(loopInfo, modifiedValues); } // Identify blocks. final IdentifyBlocksPhase s = new IdentifyBlocksPhase(false); s.apply(graph, currentContext); List<Block> blocks = s.getBlocks(); // Process blocks (predecessors first). MemoryMap[] memoryMaps = new MemoryMap[blocks.size()]; for (final Block b : blocks) { processBlock(b, memoryMaps, s.getNodeToBlock(), modifiedValues, loopInfo); } } private static void addStartCheckpoint(StructuredGraph graph) { BeginNode entryPoint = graph.start(); FixedNode next = entryPoint.next(); if (!(next instanceof MemoryCheckpoint)) { WriteMemoryCheckpointNode checkpoint = graph.add(new WriteMemoryCheckpointNode()); entryPoint.setNext(checkpoint); checkpoint.setNext(next); } } private void processBlock(Block b, MemoryMap[] memoryMaps, NodeMap<Block> nodeToBlock, HashMap<Loop, Set<Object>> modifiedValues, LoopInfo loopInfo) { // Visit every block at most once. if (memoryMaps[b.blockID()] != null) { return; } // Process predecessors before this block. for (Block pred : b.getPredecessors()) { processBlock(pred, memoryMaps, nodeToBlock, modifiedValues, loopInfo); } // 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).blockID()]); if (b.isLoopHeader()) { assert b.getPredecessors().size() == 1; Loop loop = loopInfo.loop(b.firstNode()); map.createLoopEntryMemoryMap(modifiedValues.get(loop), loop); } else { for (int i = 1; i < b.getPredecessors().size(); ++i) { assert b.firstNode() instanceof MergeNode : b.firstNode(); Block block = b.getPredecessors().get(i); map.mergeWith(memoryMaps[block.blockID()], b); } } } memoryMaps[b.blockID()] = map; // Process instructions of this block. for (Node n : b.getInstructions()) { 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.lastNode() instanceof LoopEndNode) { LoopEndNode end = (LoopEndNode) b.lastNode(); LoopBeginNode begin = end.loopBegin(); Block beginBlock = nodeToBlock.get(begin); MemoryMap memoryMap = memoryMaps[beginBlock.blockID()]; assert memoryMap != null : beginBlock.name(); assert memoryMap.getLoopEntryMap() != null; memoryMap.mergeLoopEntryWith(map, begin); } } 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); } private static void print(LoopInfo loopInfo, HashMap<Loop, Set<Object>> modifiedValues) { TTY.println(); TTY.println("Loops:"); for (Loop loop : loopInfo.loops()) { TTY.print(loop + " modified values: " + modifiedValues.get(loop)); TTY.println(); } } private void mark(LoopBeginNode begin, LoopBeginNode outer, NodeMap<LoopBeginNode> nodeToLoop) { if (nodeToLoop.get(begin) != null) { // Loop already processed. return; } nodeToLoop.set(begin, begin); NodeFlood workCFG = begin.graph().createNodeFlood(); workCFG.add(begin.loopEnd()); for (Node n : workCFG) { if (n == begin) { // Stop at loop begin. continue; } markNode(n, begin, outer, nodeToLoop); for (Node pred : n.cfgPredecessors()) { workCFG.add(pred); } } } private void markNode(Node n, LoopBeginNode begin, LoopBeginNode outer, NodeMap<LoopBeginNode> nodeToLoop) { LoopBeginNode oldMark = nodeToLoop.get(n); if (oldMark == null || oldMark == outer) { // We have an inner loop, start marking it. if (n instanceof LoopBeginNode) { mark((LoopBeginNode) n, begin, nodeToLoop); } nodeToLoop.set(n, begin); } } }