Mercurial > hg > graal-jvmci-8
changeset 19570:a33fe10c4d93
Merge.
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/ComputeBlockOrder.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/ComputeBlockOrder.java Mon Feb 23 20:13:29 2015 +0100 @@ -66,7 +66,7 @@ * * @return sorted list of blocks */ - public static <T extends AbstractBlock<T>> List<T> computeLinearScanOrder(int blockCount, T startBlock) { + public static <T extends AbstractBlockBase<T>> List<T> computeLinearScanOrder(int blockCount, T startBlock) { List<T> order = new ArrayList<>(); BitSet visitedBlocks = new BitSet(blockCount); PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks); @@ -80,7 +80,7 @@ * * @return sorted list of blocks */ - public static <T extends AbstractBlock<T>> List<T> computeCodeEmittingOrder(int blockCount, T startBlock) { + public static <T extends AbstractBlockBase<T>> List<T> computeCodeEmittingOrder(int blockCount, T startBlock) { List<T> order = new ArrayList<>(); BitSet visitedBlocks = new BitSet(blockCount); PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks); @@ -92,7 +92,7 @@ /** * Iteratively adds paths to the code emission block order. */ - private static <T extends AbstractBlock<T>> void computeCodeEmittingOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) { + private static <T extends AbstractBlockBase<T>> void computeCodeEmittingOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) { while (!worklist.isEmpty()) { T nextImportantPath = worklist.poll(); addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks); @@ -102,7 +102,7 @@ /** * Iteratively adds paths to the linear scan block order. */ - private static <T extends AbstractBlock<T>> void computeLinearScanOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) { + private static <T extends AbstractBlockBase<T>> void computeLinearScanOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) { while (!worklist.isEmpty()) { T nextImportantPath = worklist.poll(); addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks); @@ -112,7 +112,7 @@ /** * Initializes the priority queue used for the work list of blocks and adds the start block. */ - private static <T extends AbstractBlock<T>> PriorityQueue<T> initializeWorklist(T startBlock, BitSet visitedBlocks) { + private static <T extends AbstractBlockBase<T>> PriorityQueue<T> initializeWorklist(T startBlock, BitSet visitedBlocks) { PriorityQueue<T> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator<>()); result.add(startBlock); visitedBlocks.set(startBlock.getId()); @@ -122,7 +122,7 @@ /** * Add a linear path to the linear scan order greedily following the most likely successor. */ - private static <T extends AbstractBlock<T>> void addPathToLinearScanOrder(T block, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) { + private static <T extends AbstractBlockBase<T>> void addPathToLinearScanOrder(T block, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) { block.setLinearScanNumber(order.size()); order.add(block); T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks); @@ -151,7 +151,7 @@ /** * Add a linear path to the code emission order greedily following the most likely successor. */ - private static <T extends AbstractBlock<T>> void addPathToCodeEmittingOrder(T initialBlock, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) { + private static <T extends AbstractBlockBase<T>> void addPathToCodeEmittingOrder(T initialBlock, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) { T block = initialBlock; while (block != null) { // Skip loop headers if there is only a single loop end block to @@ -191,7 +191,7 @@ /** * Adds a block to the ordering. */ - private static <T extends AbstractBlock<T>> void addBlock(T header, List<T> order) { + private static <T extends AbstractBlockBase<T>> void addBlock(T header, List<T> order) { assert !order.contains(header) : "Cannot insert block twice"; order.add(header); } @@ -199,7 +199,7 @@ /** * Find the highest likely unvisited successor block of a given block. */ - private static <T extends AbstractBlock<T>> T findAndMarkMostLikelySuccessor(T block, BitSet visitedBlocks) { + private static <T extends AbstractBlockBase<T>> T findAndMarkMostLikelySuccessor(T block, BitSet visitedBlocks) { T result = null; for (T successor : block.getSuccessors()) { assert successor.probability() >= 0.0 : "Probabilities must be positive"; @@ -216,7 +216,7 @@ /** * Add successor blocks into the given work list if they are not already marked as visited. */ - private static <T extends AbstractBlock<T>> void enqueueSuccessors(T block, PriorityQueue<T> worklist, BitSet visitedBlocks) { + private static <T extends AbstractBlockBase<T>> void enqueueSuccessors(T block, PriorityQueue<T> worklist, BitSet visitedBlocks) { for (T successor : block.getSuccessors()) { if (!visitedBlocks.get(successor.getId())) { visitedBlocks.set(successor.getId()); @@ -229,14 +229,14 @@ * Skip the loop header block if the loop consists of more than one block and it has only a * single loop end block. */ - private static <T extends AbstractBlock<T>> boolean skipLoopHeader(AbstractBlock<T> block) { + private static <T extends AbstractBlockBase<T>> boolean skipLoopHeader(AbstractBlockBase<T> block) { return (block.isLoopHeader() && !block.isLoopEnd() && block.getLoop().numBackedges() == 1); } /** * Checks that the ordering contains the expected number of blocks. */ - private static boolean checkOrder(List<? extends AbstractBlock<?>> order, int expectedBlockCount) { + private static boolean checkOrder(List<? extends AbstractBlockBase<?>> order, int expectedBlockCount) { assert order.size() == expectedBlockCount : String.format("Number of blocks in ordering (%d) does not match expected block count (%d)", order.size(), expectedBlockCount); return true; } @@ -244,7 +244,7 @@ /** * Comparator for sorting blocks based on loop depth and probability. */ - private static class BlockOrderComparator<T extends AbstractBlock<T>> implements Comparator<T> { + private static class BlockOrderComparator<T extends AbstractBlockBase<T>> implements Comparator<T> { @Override public int compare(T a, T b) {
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlock.java Thu Feb 12 15:41:44 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,71 +0,0 @@ -/* - * Copyright (c) 2014, 2014, 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.common.cfg; - -import java.util.*; - -public interface AbstractBlock<T extends AbstractBlock<T>> { - - int getId(); - - Loop<T> getLoop(); - - void setLoop(Loop<T> loop); - - int getLoopDepth(); - - boolean isLoopHeader(); - - boolean isLoopEnd(); - - boolean isExceptionEntry(); - - List<T> getPredecessors(); - - int getPredecessorCount(); - - List<T> getSuccessors(); - - int getSuccessorCount(); - - int getLinearScanNumber(); - - void setLinearScanNumber(int linearScanNumber); - - boolean isAligned(); - - void setAlign(boolean align); - - T getDominator(); - - void setDominator(T block); - - List<T> getDominated(); - - void setDominated(List<T> blocks); - - T getPostdominator(); - - double probability(); - -}
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlockBase.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlockBase.java Mon Feb 23 20:13:29 2015 +0100 @@ -24,9 +24,10 @@ import java.util.*; -public abstract class AbstractBlockBase<T extends AbstractBlock<T>> implements AbstractBlock<T> { +public abstract class AbstractBlockBase<T extends AbstractBlockBase<T>> { protected int id; + protected int domDepth; protected List<T> predecessors; protected List<T> successors; @@ -72,6 +73,11 @@ public void setDominator(T dominator) { this.dominator = dominator; + this.domDepth = dominator.domDepth + 1; + } + + public int getDominatorDepth() { + return domDepth; } public List<T> getDominated() { @@ -113,4 +119,20 @@ public void setAlign(boolean align) { this.align = align; } + + public abstract boolean isExceptionEntry(); + + public abstract Loop<T> getLoop(); + + public abstract int getLoopDepth(); + + public abstract boolean isLoopEnd(); + + public abstract boolean isLoopHeader(); + + public abstract T getPostdominator(); + + public abstract double probability(); + + public abstract T getDominator(int distance); }
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java Mon Feb 23 20:13:29 2015 +0100 @@ -26,7 +26,7 @@ import com.oracle.graal.compiler.common.*; -public interface AbstractControlFlowGraph<T extends AbstractBlock<T>> { +public interface AbstractControlFlowGraph<T extends AbstractBlockBase<T>> { int BLOCK_ID_INITIAL = -1; int BLOCK_ID_VISITED = -2; @@ -48,7 +48,7 @@ /** * Computes the dominators of control flow graph. */ - static <T extends AbstractBlock<T>> void computeDominators(AbstractControlFlowGraph<T> cfg) { + static <T extends AbstractBlockBase<T>> void computeDominators(AbstractControlFlowGraph<T> cfg) { List<T> reversePostOrder = cfg.getBlocks(); assert reversePostOrder.get(0).getPredecessorCount() == 0 : "start block has no predecessor and therefore no dominator"; for (int i = 1; i < reversePostOrder.size(); i++) { @@ -72,9 +72,9 @@ /** * True if block {@code a} is dominated by block {@code b}. */ - static boolean isDominatedBy(AbstractBlock<?> a, AbstractBlock<?> b) { + static boolean isDominatedBy(AbstractBlockBase<?> a, AbstractBlockBase<?> b) { assert a != null; - AbstractBlock<?> dominator = a; + AbstractBlockBase<?> dominator = a; int i = 0; while (dominator != null) { if (i++ == Integer.MAX_VALUE) { // For safety @@ -91,7 +91,7 @@ /** * True if block {@code a} dominates block {@code b}. */ - static boolean dominates(AbstractBlock<?> a, AbstractBlock<?> b) { + static boolean dominates(AbstractBlockBase<?> a, AbstractBlockBase<?> b) { assert a != null; return isDominatedBy(b, a); } @@ -104,15 +104,24 @@ * @see #getBlocks() * @see CFGVerifier */ - static AbstractBlock<?> commonDominator(AbstractBlock<?> a, AbstractBlock<?> b) { + static AbstractBlockBase<?> commonDominator(AbstractBlockBase<?> a, AbstractBlockBase<?> b) { if (a == null) { return b; } if (b == null) { return a; } - AbstractBlock<?> iterA = a; - AbstractBlock<?> iterB = b; + + AbstractBlockBase<?> iterA = a; + AbstractBlockBase<?> iterB = b; + int aDomDepth = a.getDominatorDepth(); + int bDomDepth = b.getDominatorDepth(); + if (aDomDepth > bDomDepth) { + iterA = a.getDominator(aDomDepth - bDomDepth); + } else { + iterB = b.getDominator(bDomDepth - aDomDepth); + } + while (iterA != iterB) { if (iterA.getId() > iterB.getId()) { iterA = iterA.getDominator(); @@ -125,10 +134,10 @@ } /** - * @see AbstractControlFlowGraph#commonDominator(AbstractBlock, AbstractBlock) + * @see AbstractControlFlowGraph#commonDominator(AbstractBlockBase, AbstractBlockBase) */ @SuppressWarnings("unchecked") - static <T extends AbstractBlock<T>> T commonDominatorTyped(T a, T b) { + static <T extends AbstractBlockBase<T>> T commonDominatorTyped(T a, T b) { return (T) commonDominator(a, b); } }
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/BlockMap.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/BlockMap.java Mon Feb 23 20:13:29 2015 +0100 @@ -31,11 +31,11 @@ data = (T[]) new Object[cfg.getBlocks().size()]; } - public T get(AbstractBlock<?> block) { + public T get(AbstractBlockBase<?> block) { return data[block.getId()]; } - public void put(AbstractBlock<?> block, T value) { + public void put(AbstractBlockBase<?> block, T value) { data[block.getId()] = value; } }
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/CFGVerifier.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/CFGVerifier.java Mon Feb 23 20:13:29 2015 +0100 @@ -26,7 +26,7 @@ public class CFGVerifier { - public static <T extends AbstractBlock<T>, C extends AbstractControlFlowGraph<T>> boolean verify(C cfg) { + public static <T extends AbstractBlockBase<T>, C extends AbstractControlFlowGraph<T>> boolean verify(C cfg) { for (T block : cfg.getBlocks()) { assert block.getId() >= 0; assert cfg.getBlocks().get(block.getId()) == block;
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/DominatorOptimizationProblem.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/DominatorOptimizationProblem.java Mon Feb 23 20:13:29 2015 +0100 @@ -36,7 +36,7 @@ */ public abstract class DominatorOptimizationProblem<E extends Enum<E>, C> { - private List<? extends AbstractBlock<?>> blocks; + private List<? extends AbstractBlockBase<?>> blocks; private EnumMap<E, BitSet> flags; private BlockMap<C> costs; @@ -47,9 +47,9 @@ assert verify(blocks); } - private static boolean verify(List<? extends AbstractBlock<?>> blocks) { + private static boolean verify(List<? extends AbstractBlockBase<?>> blocks) { for (int i = 0; i < blocks.size(); i++) { - AbstractBlock<?> block = blocks.get(i); + AbstractBlockBase<?> block = blocks.get(i); if (i != block.getId()) { assert false : String.format("Id index mismatch @ %d vs. %s.getId()==%d", i, block, block.getId()); return false; @@ -58,12 +58,12 @@ return true; } - public final List<? extends AbstractBlock<?>> getBlocks() { + public final List<? extends AbstractBlockBase<?>> getBlocks() { return blocks; } - public final AbstractBlock<?> getBlockForId(int id) { - AbstractBlock<?> block = blocks.get(id); + public final AbstractBlockBase<?> getBlockForId(int id) { + AbstractBlockBase<?> block = blocks.get(id); assert block.getId() == id : "wrong block-to-id mapping"; return block; } @@ -71,7 +71,7 @@ /** * Sets a flag for a block. */ - public final void set(E flag, AbstractBlock<?> block) { + public final void set(E flag, AbstractBlockBase<?> block) { BitSet bitSet = flags.get(flag); if (bitSet == null) { bitSet = new BitSet(blocks.size()); @@ -83,7 +83,7 @@ /** * Checks whether a flag is set for a block. */ - public final boolean get(E flag, AbstractBlock<?> block) { + public final boolean get(E flag, AbstractBlockBase<?> block) { BitSet bitSet = flags.get(flag); return bitSet == null ? false : bitSet.get(block.getId()); } @@ -91,14 +91,14 @@ /** * Returns a {@linkplain Stream} of blocks for which {@code flag} is set. */ - public final Stream<? extends AbstractBlock<?>> stream(E flag) { + public final Stream<? extends AbstractBlockBase<?>> stream(E flag) { return getBlocks().stream().filter(block -> get(flag, block)); } /** * Returns the cost object associated with {@code block}. Might return {@code null} if not set. */ - public final C getCost(AbstractBlock<?> block) { + public final C getCost(AbstractBlockBase<?> block) { C cost = costs.get(block); return cost; } @@ -106,7 +106,7 @@ /** * Sets the cost for a {@code block}. */ - public final void setCost(AbstractBlock<?> block, C cost) { + public final void setCost(AbstractBlockBase<?> block, C cost) { costs.put(block, cost); } @@ -114,13 +114,13 @@ * Sets {@code flag} for all blocks along the dominator path from {@code block} to the root * until a block it finds a block where {@code flag} is already set. */ - public final void setDominatorPath(E flag, AbstractBlock<?> block) { + public final void setDominatorPath(E flag, AbstractBlockBase<?> block) { BitSet bitSet = flags.get(flag); if (bitSet == null) { bitSet = new BitSet(blocks.size()); flags.put(flag, bitSet); } - for (AbstractBlock<?> b = block; b != null && !bitSet.get(b.getId()); b = b.getDominator()) { + for (AbstractBlockBase<?> b = block; b != null && !bitSet.get(b.getId()); b = b.getDominator()) { // mark block bitSet.set(b.getId()); } @@ -129,7 +129,7 @@ /** * Returns a {@link Stream} of flags associated with {@code block}. */ - public final Stream<E> getFlagsForBlock(AbstractBlock<?> block) { + public final Stream<E> getFlagsForBlock(AbstractBlockBase<?> block) { return getFlags().stream().filter(flag -> get(flag, block)); }
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/Loop.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/Loop.java Mon Feb 23 20:13:29 2015 +0100 @@ -25,7 +25,7 @@ import java.util.*; -public abstract class Loop<T extends AbstractBlock<T>> { +public abstract class Loop<T extends AbstractBlockBase<T>> { private final Loop<T> parent; private final List<Loop<T>> children;
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PrintableCFG.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PrintableCFG.java Mon Feb 23 20:13:29 2015 +0100 @@ -31,7 +31,7 @@ */ public interface PrintableCFG { - List<? extends AbstractBlock<?>> getBlocks(); + List<? extends AbstractBlockBase<?>> getBlocks(); /** * Applies {@code action} to all extra property pairs (name, value) of {@code block}. @@ -39,7 +39,7 @@ * @param block a block from {@link #getBlocks()}. * @param action a {@link BiConsumer consumer}. */ - default void forEachPropertyPair(AbstractBlock<?> block, BiConsumer<String, String> action) { + default void forEachPropertyPair(AbstractBlockBase<?> block, BiConsumer<String, String> action) { // no extra properties per default } }
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PrintableDominatorOptimizationProblem.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PrintableDominatorOptimizationProblem.java Mon Feb 23 20:13:29 2015 +0100 @@ -33,7 +33,7 @@ super(keyType, cfg); } - public void forEachPropertyPair(AbstractBlock<?> block, BiConsumer<String, String> action) { + public void forEachPropertyPair(AbstractBlockBase<?> block, BiConsumer<String, String> action) { // for each flag getFlags().forEach(flag -> ((BiConsumer<String, Boolean>) (name, value) -> action.accept(name, value ? "true" : "false")).accept(getName(flag), get(flag, block))); // for each property
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/backend/AllocatorTest.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/backend/AllocatorTest.java Mon Feb 23 20:13:29 2015 +0100 @@ -64,7 +64,7 @@ public RegisterStats(LIR lir) { this.lir = lir; - for (AbstractBlock<?> block : lir.codeEmittingOrder()) { + for (AbstractBlockBase<?> block : lir.codeEmittingOrder()) { for (LIRInstruction instr : lir.getLIRforBlock(block)) { collectStats(instr); }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon Feb 23 20:13:29 2015 +0100 @@ -350,7 +350,7 @@ } } - public static <T extends AbstractBlock<T>> LIRGenerationResult emitLowLevel(TargetDescription target, List<T> codeEmittingOrder, List<T> linearScanOrder, LIRGenerationResult lirGenRes, + public static <T extends AbstractBlockBase<T>> LIRGenerationResult emitLowLevel(TargetDescription target, List<T> codeEmittingOrder, List<T> linearScanOrder, LIRGenerationResult lirGenRes, LIRGeneratorTool lirGen, LIRSuites lirSuites) { PreAllocationOptimizationContext preAllocOptContext = new PreAllocationOptimizationContext(lirGen); lirSuites.getPreAllocationOptimizationStage().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, preAllocOptContext);
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Edges.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Edges.java Mon Feb 23 20:13:29 2015 +0100 @@ -495,13 +495,13 @@ return type; } - public void accept(Node node, Consumer<Node> consumer) { + public void accept(Node node, BiConsumer<Node, Node> consumer) { int index = 0; int curDirectCount = this.directCount; while (index < curDirectCount) { Node curNode = getNode(node, index); if (curNode != null) { - consumer.accept(curNode); + consumer.accept(node, curNode); } index++; } @@ -512,7 +512,7 @@ for (int i = 0; i < list.size(); ++i) { Node curNode = list.get(i); if (curNode != null) { - consumer.accept(curNode); + consumer.accept(node, curNode); } } }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Mon Feb 23 20:13:29 2015 +0100 @@ -825,8 +825,8 @@ return true; } - Node getNode(int i) { - return nodes[i]; + public Node getNode(int id) { + return nodes[id]; } /**
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java Mon Feb 23 20:13:29 2015 +0100 @@ -295,7 +295,7 @@ * * @param consumer the consumer to be applied to the inputs */ - public void acceptInputs(Consumer<Node> consumer) { + public void acceptInputs(BiConsumer<Node, Node> consumer) { nodeClass.getInputEdges().accept(this, consumer); } @@ -314,7 +314,7 @@ * * @param consumer the consumer to be applied to the inputs */ - public void acceptSuccessors(Consumer<Node> consumer) { + public void acceptSuccessors(BiConsumer<Node, Node> consumer) { nodeClass.getSuccessorEdges().accept(this, consumer); } @@ -402,7 +402,7 @@ * @param node the node to remove * @return whether or not {@code usage} was in the usage list */ - private boolean removeUsage(Node node) { + public boolean removeUsage(Node node) { assert node != null; // It is critical that this method maintains the invariant that // the usage list has no null element preceding a non-null element @@ -520,12 +520,8 @@ assert assertTrue(id == INITIAL_ID, "unexpected id: %d", id); this.graph = newGraph; newGraph.register(this); - for (Node input : inputs()) { - updateUsages(null, input); - } - for (Node successor : successors()) { - updatePredecessor(null, successor); - } + this.acceptInputs((n, i) -> n.updateUsages(null, i)); + this.acceptSuccessors((n, s) -> n.updatePredecessor(null, s)); } public final NodeClass<? extends Node> getNodeClass() { @@ -677,7 +673,7 @@ } private void unregisterSuccessors() { - this.acceptSuccessors(successor -> successor.predecessor = null); + this.acceptSuccessors((n, successor) -> successor.predecessor = null); } public void clearSuccessors() { @@ -699,12 +695,12 @@ */ public void safeDelete() { assert checkDeletion(); - unsafeDelete(); + unregisterInputs(); + unregisterSuccessors(); + markDeleted(); } - public void unsafeDelete() { - unregisterInputs(); - unregisterSuccessors(); + public void markDeleted() { graph.unregister(this); id = DELETED_ID_START - id; assert isDeleted();
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java Mon Feb 23 20:13:29 2015 +0100 @@ -60,6 +60,10 @@ public boolean isMarked(Node node) { assert check(node, false); int id = nodeIdAccessor.getNodeId(node); + return isMarked(id); + } + + public boolean isMarked(int id) { return (bits[id >> SHIFT] & (1L << id)) != 0; } @@ -67,7 +71,7 @@ assert check(node, true); int id = nodeIdAccessor.getNodeId(node); checkGrow(id); - return (bits[id >> SHIFT] & (1L << id)) != 0; + return isMarked(id); } public void mark(Node node) {
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Mon Feb 23 20:13:29 2015 +0100 @@ -569,16 +569,18 @@ static void updateEdgesInPlace(Node node, InplaceUpdateClosure duplicationReplacement, Edges edges) { int index = 0; - while (index < edges.getDirectCount()) { + Type curType = edges.type(); + int directCount = edges.getDirectCount(); + while (index < directCount) { Node edge = edges.getNode(node, index); if (edge != null) { - Node newEdge = duplicationReplacement.replacement(edge, edges.type()); - if (edges.type() == Edges.Type.Inputs) { + Node newEdge = duplicationReplacement.replacement(edge, curType); + if (curType == Edges.Type.Inputs) { node.updateUsages(null, newEdge); } else { node.updatePredecessor(null, newEdge); } - assert newEdge == null || edges.getType(index).isAssignableFrom(newEdge.getClass()) : "Can not assign " + newEdge.getClass() + " to " + edges.getType(index) + " in " + node; + assert assertUpdateValid(node, edges, index, newEdge); edges.initializeNode(node, index, newEdge); } index++; @@ -587,12 +589,17 @@ while (index < edges.getCount()) { NodeList<Node> list = edges.getNodeList(node, index); if (list != null) { - edges.initializeList(node, index, updateEdgeListCopy(node, list, duplicationReplacement, edges.type())); + edges.initializeList(node, index, updateEdgeListCopy(node, list, duplicationReplacement, curType)); } index++; } } + private static boolean assertUpdateValid(Node node, Edges edges, int index, Node newEdge) { + assert newEdge == null || edges.getType(index).isAssignableFrom(newEdge.getClass()) : "Can not assign " + newEdge.getClass() + " to " + edges.getType(index) + " in " + node; + return true; + } + void updateInputSuccInPlace(Node node, InplaceUpdateClosure duplicationReplacement) { updateEdgesInPlace(node, duplicationReplacement, inputs); updateEdgesInPlace(node, duplicationReplacement, successors);
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeFlood.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeFlood.java Mon Feb 23 20:13:29 2015 +0100 @@ -24,10 +24,11 @@ import java.util.*; -public class NodeFlood implements Iterable<Node> { +public final class NodeFlood implements Iterable<Node> { private final NodeBitMap visited; private final Queue<Node> worklist; + private int totalMarkedCount; public NodeFlood(Graph graph) { visited = graph.createNodeBitMap(); @@ -38,15 +39,24 @@ if (node != null && !visited.isMarked(node)) { visited.mark(node); worklist.add(node); + totalMarkedCount++; } } + public int getTotalMarkedCount() { + return totalMarkedCount; + } + public void addAll(Iterable<? extends Node> nodes) { for (Node node : nodes) { this.add(node); } } + public NodeBitMap getVisited() { + return visited; + } + public boolean isMarked(Node node) { return visited.isMarked(node); }
--- a/graal/com.oracle.graal.hotspot.sparc/src/com/oracle/graal/hotspot/sparc/SPARCHotSpotBackend.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.hotspot.sparc/src/com/oracle/graal/hotspot/sparc/SPARCHotSpotBackend.java Mon Feb 23 20:13:29 2015 +0100 @@ -273,7 +273,7 @@ } private static void resetDelayedControlTransfers(LIR lir) { - for (AbstractBlock<?> block : lir.codeEmittingOrder()) { + for (AbstractBlockBase<?> block : lir.codeEmittingOrder()) { for (LIRInstruction inst : lir.getLIRforBlock(block)) { if (inst instanceof SPARCDelayedControlTransfer) { ((SPARCDelayedControlTransfer) inst).resetState(); @@ -285,11 +285,11 @@ /** * Fix-up over whole LIR. * - * @see #stuffDelayedControlTransfers(LIR, AbstractBlock) + * @see #stuffDelayedControlTransfers(LIR, AbstractBlockBase) * @param l */ private static void stuffDelayedControlTransfers(LIR l) { - for (AbstractBlock<?> b : l.codeEmittingOrder()) { + for (AbstractBlockBase<?> b : l.codeEmittingOrder()) { stuffDelayedControlTransfers(l, b); } } @@ -299,7 +299,7 @@ * it tries to move the DelayedLIRInstruction to the DelayedControlTransfer instruction, if * possible. */ - private static void stuffDelayedControlTransfers(LIR l, AbstractBlock<?> block) { + private static void stuffDelayedControlTransfers(LIR l, AbstractBlockBase<?> block) { List<LIRInstruction> instructions = l.getLIRforBlock(block); if (instructions.size() >= 2) { LIRDependencyAccumulator acc = new LIRDependencyAccumulator();
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotBackend.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotBackend.java Mon Feb 23 20:13:29 2015 +0100 @@ -172,7 +172,7 @@ } } }; - for (AbstractBlock<?> block : lir.codeEmittingOrder()) { + for (AbstractBlockBase<?> block : lir.codeEmittingOrder()) { for (LIRInstruction op : lir.getLIRforBlock(block)) { if (op instanceof LabelOp) { // Don't consider this as a definition
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ControlFlowOptimizer.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ControlFlowOptimizer.java Mon Feb 23 20:13:29 2015 +0100 @@ -41,12 +41,12 @@ * Performs control flow optimizations on the given LIR graph. */ @Override - protected <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder) { + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder) { LIR lir = lirGenRes.getLIR(); new Optimizer<B>(lir).deleteEmptyBlocks(codeEmittingOrder); } - private static final class Optimizer<B extends AbstractBlock<B>> { + private static final class Optimizer<B extends AbstractBlockBase<B>> { private final LIR lir; @@ -97,7 +97,7 @@ if (canDeleteBlock(block)) { // adjust successor and predecessor lists B other = block.getSuccessors().iterator().next(); - for (AbstractBlock<B> pred : block.getPredecessors()) { + for (AbstractBlockBase<B> pred : block.getPredecessors()) { Collections.replaceAll(pred.getSuccessors(), block, other); } for (int i = 0; i < other.getPredecessorCount(); i++) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/EdgeMoveOptimizer.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/EdgeMoveOptimizer.java Mon Feb 23 20:13:29 2015 +0100 @@ -51,14 +51,14 @@ public final class EdgeMoveOptimizer extends PostAllocationOptimizationPhase { @Override - protected <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder) { + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder) { LIR ir = lirGenRes.getLIR(); Optimizer optimizer = new Optimizer(ir); - List<? extends AbstractBlock<?>> blockList = ir.linearScanOrder(); + List<? extends AbstractBlockBase<?>> blockList = ir.linearScanOrder(); // ignore the first block in the list (index 0 is not processed) for (int i = blockList.size() - 1; i >= 1; i--) { - AbstractBlock<?> block = blockList.get(i); + AbstractBlockBase<?> block = blockList.get(i); if (block.getPredecessorCount() > 1) { optimizer.optimizeMovesAtBlockEnd(block); @@ -106,8 +106,8 @@ * Moves the longest {@linkplain #same common} subsequence at the end all predecessors of * {@code block} to the start of {@code block}. */ - private void optimizeMovesAtBlockEnd(AbstractBlock<?> block) { - for (AbstractBlock<?> pred : block.getPredecessors()) { + private void optimizeMovesAtBlockEnd(AbstractBlockBase<?> block) { + for (AbstractBlockBase<?> pred : block.getPredecessors()) { if (pred == block) { // currently we can't handle this correctly. return; @@ -121,7 +121,7 @@ assert numPreds > 1 : "do not call otherwise"; // setup a list with the LIR instructions of all predecessors - for (AbstractBlock<?> pred : block.getPredecessors()) { + for (AbstractBlockBase<?> pred : block.getPredecessors()) { assert pred != null; assert ir.getLIRforBlock(pred) != null; List<LIRInstruction> predInstructions = ir.getLIRforBlock(pred); @@ -176,7 +176,7 @@ * {@code block} to the end of {@code block} just prior to the branch instruction ending * {@code block}. */ - private void optimizeMovesAtBlockBegin(AbstractBlock<?> block) { + private void optimizeMovesAtBlockBegin(AbstractBlockBase<?> block) { edgeInstructionSeqences.clear(); int numSux = block.getSuccessorCount(); @@ -206,7 +206,7 @@ int insertIdx = instructions.size() - 1; // setup a list with the lir-instructions of all successors - for (AbstractBlock<?> sux : block.getSuccessors()) { + for (AbstractBlockBase<?> sux : block.getSuccessors()) { List<LIRInstruction> suxInstructions = ir.getLIRforBlock(sux); assert suxInstructions.get(0) instanceof StandardOp.LabelOp : "block must start with label";
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java Mon Feb 23 20:13:29 2015 +0100 @@ -39,12 +39,12 @@ /** * The linear-scan ordered list of blocks. */ - private final List<? extends AbstractBlock<?>> linearScanOrder; + private final List<? extends AbstractBlockBase<?>> linearScanOrder; /** * The order in which the code is emitted. */ - private final List<? extends AbstractBlock<?>> codeEmittingOrder; + private final List<? extends AbstractBlockBase<?>> codeEmittingOrder; private int firstVariableNumber; @@ -57,7 +57,7 @@ /** * Creates a new LIR instance for the specified compilation. */ - public LIR(AbstractControlFlowGraph<?> cfg, List<? extends AbstractBlock<?>> linearScanOrder, List<? extends AbstractBlock<?>> codeEmittingOrder) { + public LIR(AbstractControlFlowGraph<?> cfg, List<? extends AbstractBlockBase<?>> linearScanOrder, List<? extends AbstractBlockBase<?>> codeEmittingOrder) { this.cfg = cfg; this.codeEmittingOrder = codeEmittingOrder; this.linearScanOrder = linearScanOrder; @@ -72,7 +72,7 @@ * Determines if any instruction in the LIR has debug info associated with it. */ public boolean hasDebugInfo() { - for (AbstractBlock<?> b : linearScanOrder()) { + for (AbstractBlockBase<?> b : linearScanOrder()) { for (LIRInstruction op : getLIRforBlock(b)) { if (op.hasState()) { return true; @@ -82,11 +82,11 @@ return false; } - public List<LIRInstruction> getLIRforBlock(AbstractBlock<?> block) { + public List<LIRInstruction> getLIRforBlock(AbstractBlockBase<?> block) { return lirInstructions.get(block); } - public void setLIRforBlock(AbstractBlock<?> block, List<LIRInstruction> list) { + public void setLIRforBlock(AbstractBlockBase<?> block, List<LIRInstruction> list) { assert getLIRforBlock(block) == null : "lir instruction list should only be initialized once"; lirInstructions.put(block, list); } @@ -96,11 +96,11 @@ * * @return the blocks in linear scan order */ - public List<? extends AbstractBlock<?>> linearScanOrder() { + public List<? extends AbstractBlockBase<?>> linearScanOrder() { return linearScanOrder; } - public List<? extends AbstractBlock<?>> codeEmittingOrder() { + public List<? extends AbstractBlockBase<?>> codeEmittingOrder() { return codeEmittingOrder; } @@ -154,7 +154,7 @@ */ public static final int MAX_EXCEPTION_EDGE_OP_DISTANCE_FROM_END = 3; - public static boolean verifyBlock(LIR lir, AbstractBlock<?> block) { + public static boolean verifyBlock(LIR lir, AbstractBlockBase<?> block) { List<LIRInstruction> ops = lir.getLIRforBlock(block); if (ops.size() == 0) { return false; @@ -178,12 +178,12 @@ return true; } - public static boolean verifyBlocks(LIR lir, List<? extends AbstractBlock<?>> blocks) { - for (AbstractBlock<?> block : blocks) { - for (AbstractBlock<?> sux : block.getSuccessors()) { + public static boolean verifyBlocks(LIR lir, List<? extends AbstractBlockBase<?>> blocks) { + for (AbstractBlockBase<?> block : blocks) { + for (AbstractBlockBase<?> sux : block.getSuccessors()) { assert blocks.contains(sux) : "missing successor from: " + block + "to: " + sux; } - for (AbstractBlock<?> pred : block.getPredecessors()) { + for (AbstractBlockBase<?> pred : block.getPredecessors()) { assert blocks.contains(pred) : "missing predecessor from: " + block + "to: " + pred; } if (!verifyBlock(lir, block)) { @@ -195,7 +195,7 @@ public void resetLabels() { - for (AbstractBlock<?> block : codeEmittingOrder()) { + for (AbstractBlockBase<?> block : codeEmittingOrder()) { for (LIRInstruction inst : lirInstructions.get(block)) { if (inst instanceof LabelOp) { ((LabelOp) inst).getLabel().reset();
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRVerifier.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRVerifier.java Mon Feb 23 20:13:29 2015 +0100 @@ -46,11 +46,11 @@ private final BitSet[] blockLiveOut; private final Object[] variableDefinitions; - private BitSet liveOutFor(AbstractBlock<?> block) { + private BitSet liveOutFor(AbstractBlockBase<?> block) { return blockLiveOut[block.getId()]; } - private void setLiveOutFor(AbstractBlock<?> block, BitSet liveOut) { + private void setLiveOutFor(AbstractBlockBase<?> block, BitSet liveOut) { blockLiveOut[block.getId()] = liveOut; } @@ -91,7 +91,7 @@ private BitSet curVariablesLive; private Value[] curRegistersLive; - private AbstractBlock<?> curBlock; + private AbstractBlockBase<?> curBlock; private Object curInstruction; private BitSet curRegistersDefined; @@ -113,7 +113,7 @@ int maxRegisterNum = maxRegisterNum(); curRegistersDefined = new BitSet(); - for (AbstractBlock<?> block : lir.linearScanOrder()) { + for (AbstractBlockBase<?> block : lir.linearScanOrder()) { curBlock = block; curVariablesLive = new BitSet(); curRegistersLive = new Value[maxRegisterNum];
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LabelRef.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LabelRef.java Mon Feb 23 20:13:29 2015 +0100 @@ -29,7 +29,7 @@ /** * LIR instructions such as {@link JumpOp} and {@link BranchOp} need to reference their target - * {@link AbstractBlock}. However, direct references are not possible since the control flow graph + * {@link AbstractBlockBase}. However, direct references are not possible since the control flow graph * (and therefore successors lists) can be changed by optimizations - and fixing the instructions is * error prone. Therefore, we represent an edge to block B from block A via the tuple {@code (A, * successor-index-of-B)}. That is, indirectly by storing the index into the successor list of A. @@ -38,7 +38,7 @@ public final class LabelRef { private final LIR lir; - private final AbstractBlock<?> block; + private final AbstractBlockBase<?> block; private final int suxIndex; /** @@ -48,7 +48,7 @@ * @param suxIndex The index of the successor. * @return The newly created label reference. */ - public static LabelRef forSuccessor(final LIR lir, final AbstractBlock<?> block, final int suxIndex) { + public static LabelRef forSuccessor(final LIR lir, final AbstractBlockBase<?> block, final int suxIndex) { return new LabelRef(lir, block, suxIndex); } @@ -58,17 +58,17 @@ * @param block The base block that contains the successor list. * @param suxIndex The index of the successor. */ - private LabelRef(final LIR lir, final AbstractBlock<?> block, final int suxIndex) { + private LabelRef(final LIR lir, final AbstractBlockBase<?> block, final int suxIndex) { this.lir = lir; this.block = block; this.suxIndex = suxIndex; } - public AbstractBlock<?> getSourceBlock() { + public AbstractBlockBase<?> getSourceBlock() { return block; } - public AbstractBlock<?> getTargetBlock() { + public AbstractBlockBase<?> getTargetBlock() { return block.getSuccessors().get(suxIndex); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/NullCheckOptimizer.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/NullCheckOptimizer.java Mon Feb 23 20:13:29 2015 +0100 @@ -34,14 +34,14 @@ public final class NullCheckOptimizer extends PostAllocationOptimizationPhase { @Override - protected <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder) { + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder) { LIR ir = lirGenRes.getLIR(); - List<? extends AbstractBlock<?>> blocks = ir.codeEmittingOrder(); + List<? extends AbstractBlockBase<?>> blocks = ir.codeEmittingOrder(); NullCheckOptimizer.foldNullChecks(ir, blocks, target.implicitNullCheckLimit); } - private static void foldNullChecks(LIR ir, List<? extends AbstractBlock<?>> blocks, int implicitNullCheckLimit) { - for (AbstractBlock<?> block : blocks) { + private static void foldNullChecks(LIR ir, List<? extends AbstractBlockBase<?>> blocks, int implicitNullCheckLimit) { + for (AbstractBlockBase<?> block : blocks) { List<LIRInstruction> list = ir.getLIRforBlock(block); if (!list.isEmpty()) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/RedundantMoveElimination.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/RedundantMoveElimination.java Mon Feb 23 20:13:29 2015 +0100 @@ -44,7 +44,7 @@ public final class RedundantMoveElimination extends PostAllocationOptimizationPhase { @Override - protected <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder) { + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder) { Optimization redundantMoveElimination = new Optimization(); redundantMoveElimination.doOptimize(lirGenRes.getLIR(), lirGenRes.getFrameMap()); } @@ -87,7 +87,7 @@ private static final class Optimization { - Map<AbstractBlock<?>, BlockData> blockData = CollectionsFactory.newMap(); + Map<AbstractBlockBase<?>, BlockData> blockData = CollectionsFactory.newMap(); Register[] callerSaveRegs; @@ -142,7 +142,7 @@ private void initBlockData(LIR lir) { - List<? extends AbstractBlock<?>> blocks = lir.linearScanOrder(); + List<? extends AbstractBlockBase<?>> blocks = lir.linearScanOrder(); numRegs = 0; int maxStackLocations = COMPLEXITY_LIMIT / blocks.size(); @@ -151,7 +151,7 @@ * Search for relevant locations which can be optimized. These are register or stack * slots which occur as destinations of move instructions. */ - for (AbstractBlock<?> block : blocks) { + for (AbstractBlockBase<?> block : blocks) { List<LIRInstruction> instructions = lir.getLIRforBlock(block); for (LIRInstruction op : instructions) { if (isEligibleMove(op)) { @@ -176,7 +176,7 @@ */ int numLocations = numRegs + stackIndices.size(); Debug.log("num locations = %d (regs = %d, stack = %d)", numLocations, numRegs, stackIndices.size()); - for (AbstractBlock<?> block : blocks) { + for (AbstractBlockBase<?> block : blocks) { BlockData data = new BlockData(numLocations); blockData.put(block, data); } @@ -191,7 +191,7 @@ try (Indent indent = Debug.logAndIndent("solve data flow")) { - List<? extends AbstractBlock<?>> blocks = lir.linearScanOrder(); + List<? extends AbstractBlockBase<?>> blocks = lir.linearScanOrder(); int numIter = 0; @@ -205,7 +205,7 @@ changed = false; try (Indent indent2 = Debug.logAndIndent("new iteration")) { - for (AbstractBlock<?> block : blocks) { + for (AbstractBlockBase<?> block : blocks) { BlockData data = blockData.get(block); /* @@ -235,7 +235,7 @@ /* * Merge the states of predecessor blocks */ - for (AbstractBlock<?> predecessor : block.getPredecessors()) { + for (AbstractBlockBase<?> predecessor : block.getPredecessors()) { BlockData predData = blockData.get(predecessor); newState |= mergeState(data.entryState, predData.exitState, valueNum); } @@ -291,9 +291,9 @@ try (Indent indent = Debug.logAndIndent("eliminate moves")) { - List<? extends AbstractBlock<?>> blocks = lir.linearScanOrder(); + List<? extends AbstractBlockBase<?>> blocks = lir.linearScanOrder(); - for (AbstractBlock<?> block : blocks) { + for (AbstractBlockBase<?> block : blocks) { try (Indent indent2 = Debug.logAndIndent("eliminate moves in block %d", block.getId())) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/StandardOp.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/StandardOp.java Mon Feb 23 20:13:29 2015 +0100 @@ -192,14 +192,14 @@ /** * The block in which this instruction is located. */ - final AbstractBlock<?> block; + final AbstractBlockBase<?> block; /** * The block index of this instruction. */ final int index; - public NoOp(AbstractBlock<?> block, int index) { + public NoOp(AbstractBlockBase<?> block, int index) { super(TYPE); this.block = block; this.index = index;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/IntervalWalker.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/IntervalWalker.java Mon Feb 23 20:13:29 2015 +0100 @@ -104,63 +104,65 @@ private void walkTo(State state, int from) { assert state == State.Active || state == State.Inactive : "wrong state"; for (RegisterBinding binding : RegisterBinding.VALUES) { - Interval prevprev = null; - Interval prev = (state == State.Active) ? activeLists.get(binding) : inactiveLists.get(binding); - Interval next = prev; - while (next.currentFrom() <= from) { - Interval cur = next; - next = cur.next; + walkTo(state, from, binding); + } + } - boolean rangeHasChanged = false; - while (cur.currentTo() <= from) { - cur.nextRange(); - rangeHasChanged = true; - } + private void walkTo(State state, int from, RegisterBinding binding) { + Interval prevprev = null; + Interval prev = (state == State.Active) ? activeLists.get(binding) : inactiveLists.get(binding); + Interval next = prev; + while (next.currentFrom() <= from) { + Interval cur = next; + next = cur.next; - // also handle move from inactive list to active list - rangeHasChanged = rangeHasChanged || (state == State.Inactive && cur.currentFrom() <= from); + boolean rangeHasChanged = false; + while (cur.currentTo() <= from) { + cur.nextRange(); + rangeHasChanged = true; + } - if (rangeHasChanged) { - // remove cur from list - if (prevprev == null) { - if (state == State.Active) { - activeLists.set(binding, next); - } else { - inactiveLists.set(binding, next); - } + // also handle move from inactive list to active list + rangeHasChanged = rangeHasChanged || (state == State.Inactive && cur.currentFrom() <= from); + + if (rangeHasChanged) { + // remove cur from list + if (prevprev == null) { + if (state == State.Active) { + activeLists.set(binding, next); } else { - prevprev.next = next; + inactiveLists.set(binding, next); } - prev = next; - if (cur.currentAtEnd()) { - // move to handled state (not maintained as a list) - cur.state = State.Handled; - intervalMoved(cur, state, State.Handled); - } else if (cur.currentFrom() <= from) { + } else { + prevprev.next = next; + } + prev = next; + Interval.State newState; + if (cur.currentAtEnd()) { + // move to handled state (not maintained as a list) + newState = State.Handled; + cur.state = newState; + } else { + if (cur.currentFrom() <= from) { // sort into active list activeLists.addToListSortedByCurrentFromPositions(binding, cur); - cur.state = State.Active; - if (prev == cur) { - assert state == State.Active : "check"; - prevprev = prev; - prev = cur.next; - } - intervalMoved(cur, state, State.Active); + newState = State.Active; } else { // sort into inactive list inactiveLists.addToListSortedByCurrentFromPositions(binding, cur); - cur.state = State.Inactive; - if (prev == cur) { - assert state == State.Inactive : "check"; - prevprev = prev; - prev = cur.next; - } - intervalMoved(cur, state, State.Inactive); + newState = State.Inactive; } - } else { - prevprev = prev; - prev = cur.next; + cur.state = newState; + if (prev == cur) { + assert state == newState; + prevprev = prev; + prev = cur.next; + } } + intervalMoved(cur, state, newState); + } else { + prevprev = prev; + prev = cur.next; } } }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java Mon Feb 23 20:13:29 2015 +0100 @@ -116,7 +116,7 @@ /** * List of blocks in linear-scan order. This is only correct as long as the CFG does not change. */ - final List<? extends AbstractBlock<?>> sortedBlocks; + final List<? extends AbstractBlockBase<?>> sortedBlocks; /** * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals. @@ -147,11 +147,11 @@ LIRInstruction[] opIdToInstructionMap; /** - * Map from an instruction {@linkplain LIRInstruction#id id} to the {@linkplain AbstractBlock + * Map from an instruction {@linkplain LIRInstruction#id id} to the {@linkplain AbstractBlockBase * block} containing the instruction. Entries should be retrieved with {@link #blockForId(int)} * as the id is not simply an index into this array. */ - AbstractBlock<?>[] opIdToBlockMap; + AbstractBlockBase<?>[] opIdToBlockMap; /** * Bit set for each variable that is contained in each loop. @@ -181,13 +181,13 @@ this.callKillsRegisters = this.frameMapBuilder.getRegisterConfig().areAllAllocatableRegistersCallerSaved(); } - int getFirstLirInstructionId(AbstractBlock<?> block) { + int getFirstLirInstructionId(AbstractBlockBase<?> block) { int result = ir.getLIRforBlock(block).get(0).id(); assert result >= 0; return result; } - int getLastLirInstructionId(AbstractBlock<?> block) { + int getLastLirInstructionId(AbstractBlockBase<?> block) { List<LIRInstruction> instructions = ir.getLIRforBlock(block); int result = instructions.get(instructions.size() - 1).id(); assert result >= 0; @@ -319,7 +319,7 @@ return sortedBlocks.size(); } - AbstractBlock<?> blockAt(int index) { + AbstractBlockBase<?> blockAt(int index) { return sortedBlocks.get(index); } @@ -395,7 +395,7 @@ * @param opId an instruction {@linkplain LIRInstruction#id id} * @return the block containing the instruction denoted by {@code opId} */ - AbstractBlock<?> blockForId(int opId) { + AbstractBlockBase<?> blockForId(int opId) { assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range"; return opIdToBlockMap[opIdToIndex(opId)]; } @@ -529,7 +529,7 @@ } LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer(); - for (AbstractBlock<?> block : sortedBlocks) { + for (AbstractBlockBase<?> block : sortedBlocks) { List<LIRInstruction> instructions = ir.getLIRforBlock(block); int numInst = instructions.size(); @@ -634,17 +634,17 @@ // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node. int numInstructions = 0; - for (AbstractBlock<?> block : sortedBlocks) { + for (AbstractBlockBase<?> block : sortedBlocks) { numInstructions += ir.getLIRforBlock(block).size(); } // initialize with correct length opIdToInstructionMap = new LIRInstruction[numInstructions]; - opIdToBlockMap = new AbstractBlock<?>[numInstructions]; + opIdToBlockMap = new AbstractBlockBase<?>[numInstructions]; int opId = 0; int index = 0; - for (AbstractBlock<?> block : sortedBlocks) { + for (AbstractBlockBase<?> block : sortedBlocks) { blockData.put(block, new BlockData()); List<LIRInstruction> instructions = ir.getLIRforBlock(block); @@ -679,7 +679,7 @@ intervalInLoop = new BitMap2D(operandSize(), numLoops()); // iterate all blocks - for (final AbstractBlock<?> block : sortedBlocks) { + for (final AbstractBlockBase<?> block : sortedBlocks) { try (Indent indent = Debug.logAndIndent("compute local live sets for block %d", block.getId())) { final BitSet liveGen = new BitSet(liveSize); @@ -770,7 +770,7 @@ } } - private void verifyInput(AbstractBlock<?> block, BitSet liveKill, Value operand) { + private void verifyInput(AbstractBlockBase<?> block, BitSet liveKill, Value operand) { // fixed intervals are never live at block boundaries, so // they need not be processed in live sets. // this is checked by these assertions to be sure about it. @@ -804,7 +804,7 @@ // iterate all blocks in reverse order for (int i = numBlocks - 1; i >= 0; i--) { - AbstractBlock<?> block = blockAt(i); + AbstractBlockBase<?> block = blockAt(i); BlockData blockSets = blockData.get(block); changeOccurredInBlock = false; @@ -815,7 +815,7 @@ liveOut.clear(); // block has successors if (n > 0) { - for (AbstractBlock<?> successor : block.getSuccessors()) { + for (AbstractBlockBase<?> successor : block.getSuccessors()) { liveOut.or(blockData.get(successor).liveIn); } } @@ -859,7 +859,7 @@ } // check that the liveIn set of the first block is empty - AbstractBlock<?> startBlock = ir.getControlFlowGraph().getStartBlock(); + AbstractBlockBase<?> startBlock = ir.getControlFlowGraph().getStartBlock(); if (blockData.get(startBlock).liveIn.cardinality() != 0) { if (DetailedAsserts.getValue()) { reportFailure(numBlocks); @@ -898,9 +898,9 @@ } try (Indent indent2 = Debug.logAndIndent("---- Detailed information for var %d; operand=%s; node=%s ----", operandNum, operand, valueForOperandFromDebugContext)) { - Deque<AbstractBlock<?>> definedIn = new ArrayDeque<>(); - HashSet<AbstractBlock<?>> usedIn = new HashSet<>(); - for (AbstractBlock<?> block : sortedBlocks) { + Deque<AbstractBlockBase<?>> definedIn = new ArrayDeque<>(); + HashSet<AbstractBlockBase<?>> usedIn = new HashSet<>(); + for (AbstractBlockBase<?> block : sortedBlocks) { if (blockData.get(block).liveGen.get(operandNum)) { usedIn.add(block); try (Indent indent3 = Debug.logAndIndent("used in block B%d", block.getId())) { @@ -927,9 +927,9 @@ int[] hitCount = new int[numBlocks]; while (!definedIn.isEmpty()) { - AbstractBlock<?> block = definedIn.removeFirst(); + AbstractBlockBase<?> block = definedIn.removeFirst(); usedIn.remove(block); - for (AbstractBlock<?> successor : block.getSuccessors()) { + for (AbstractBlockBase<?> successor : block.getSuccessors()) { if (successor.isLoopHeader()) { if (!block.isLoopEnd()) { definedIn.add(successor); @@ -942,7 +942,7 @@ } } try (Indent indent3 = Debug.logAndIndent("**** offending usages are in: ")) { - for (AbstractBlock<?> block : usedIn) { + for (AbstractBlockBase<?> block : usedIn) { Debug.log("B%d", block.getId()); } } @@ -957,7 +957,7 @@ private void verifyLiveness() { // check that fixed intervals are not live at block boundaries // (live set must be empty at fixed intervals) - for (AbstractBlock<?> block : sortedBlocks) { + for (AbstractBlockBase<?> block : sortedBlocks) { for (int j = 0; j <= maxRegisterNumber(); j++) { assert !blockData.get(block).liveIn.get(j) : "liveIn set of fixed register must be empty"; assert !blockData.get(block).liveOut.get(j) : "liveOut set of fixed register must be empty"; @@ -1174,7 +1174,7 @@ // iterate all blocks in reverse order for (int i = blockCount() - 1; i >= 0; i--) { - AbstractBlock<?> block = blockAt(i); + AbstractBlockBase<?> block = blockAt(i); try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) { List<LIRInstruction> instructions = ir.getLIRforBlock(block); @@ -1418,15 +1418,15 @@ throw new BailoutException("LinearScan: interval is null"); } - Interval intervalAtBlockBegin(AbstractBlock<?> block, int operandNumber) { + Interval intervalAtBlockBegin(AbstractBlockBase<?> block, int operandNumber) { return splitChildAtOpId(intervalFor(operandNumber), getFirstLirInstructionId(block), LIRInstruction.OperandMode.DEF); } - Interval intervalAtBlockEnd(AbstractBlock<?> block, int operandNumber) { + Interval intervalAtBlockEnd(AbstractBlockBase<?> block, int operandNumber) { return splitChildAtOpId(intervalFor(operandNumber), getLastLirInstructionId(block) + 1, LIRInstruction.OperandMode.DEF); } - void resolveCollectMappings(AbstractBlock<?> fromBlock, AbstractBlock<?> toBlock, MoveResolver moveResolver) { + void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, MoveResolver moveResolver) { assert moveResolver.checkEmpty(); int numOperands = operandSize(); @@ -1447,7 +1447,7 @@ } } - void resolveFindInsertPos(AbstractBlock<?> fromBlock, AbstractBlock<?> toBlock, MoveResolver moveResolver) { + void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, MoveResolver moveResolver) { if (fromBlock.getSuccessorCount() <= 1) { Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId()); @@ -1470,7 +1470,7 @@ // successor edges, blocks which are reached by switch statements // may have be more than one predecessor but it will be guaranteed // that all predecessors will be the same. - for (AbstractBlock<?> predecessor : toBlock.getPredecessors()) { + for (AbstractBlockBase<?> predecessor : toBlock.getPredecessors()) { assert fromBlock == predecessor : "all critical edges must be broken"; } } @@ -1491,7 +1491,7 @@ BitSet blockCompleted = new BitSet(numBlocks); BitSet alreadyResolved = new BitSet(numBlocks); - for (AbstractBlock<?> block : sortedBlocks) { + for (AbstractBlockBase<?> block : sortedBlocks) { // check if block has only one predecessor and only one successor if (block.getPredecessorCount() == 1 && block.getSuccessorCount() == 1) { @@ -1501,8 +1501,8 @@ // check if block is empty (only label and branch) if (instructions.size() == 2) { - AbstractBlock<?> pred = block.getPredecessors().iterator().next(); - AbstractBlock<?> sux = block.getSuccessors().iterator().next(); + AbstractBlockBase<?> pred = block.getPredecessors().iterator().next(); + AbstractBlockBase<?> sux = block.getSuccessors().iterator().next(); // prevent optimization of two consecutive blocks if (!blockCompleted.get(pred.getLinearScanNumber()) && !blockCompleted.get(sux.getLinearScanNumber())) { @@ -1523,12 +1523,12 @@ } } - for (AbstractBlock<?> fromBlock : sortedBlocks) { + for (AbstractBlockBase<?> fromBlock : sortedBlocks) { if (!blockCompleted.get(fromBlock.getLinearScanNumber())) { alreadyResolved.clear(); alreadyResolved.or(blockCompleted); - for (AbstractBlock<?> toBlock : fromBlock.getSuccessors()) { + for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) { // check for duplicate edges between the same blocks (can happen with switch // blocks) @@ -1573,7 +1573,7 @@ if (opId != -1) { if (DetailedAsserts.getValue()) { - AbstractBlock<?> block = blockForId(opId); + AbstractBlockBase<?> block = blockForId(opId); if (block.getSuccessorCount() <= 1 && opId == getLastLirInstructionId(block)) { // check if spill moves could have been appended at the end of this block, but // before the branch instruction. So the split child information for this branch @@ -1646,7 +1646,7 @@ } int tempOpId = op.id(); OperandMode mode = OperandMode.USE; - AbstractBlock<?> block = blockForId(tempOpId); + AbstractBlockBase<?> block = blockForId(tempOpId); if (block.getSuccessorCount() == 1 && tempOpId == getLastLirInstructionId(block)) { // generating debug information for the last instruction of a block. // if this instruction is a branch, spill moves are inserted before this branch @@ -1730,7 +1730,7 @@ private void assignLocations() { try (Indent indent = Debug.logAndIndent("assign locations")) { - for (AbstractBlock<?> block : sortedBlocks) { + for (AbstractBlockBase<?> block : sortedBlocks) { try (Indent indent2 = Debug.logAndIndent("assign locations in block B%d", block.getId())) { assignLocations(ir.getLIRforBlock(block)); } @@ -1818,8 +1818,8 @@ LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[ir.linearScanOrder().size()]; for (Interval interval : intervals) { if (interval != null && interval.isSplitParent() && interval.spillState() == SpillState.SpillInDominator) { - AbstractBlock<?> defBlock = blockForId(interval.spillDefinitionPos()); - AbstractBlock<?> spillBlock = null; + AbstractBlockBase<?> defBlock = blockForId(interval.spillDefinitionPos()); + AbstractBlockBase<?> spillBlock = null; Interval firstSpillChild = null; try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) { for (Interval splitChild : interval.getSplitChildren()) { @@ -1830,7 +1830,7 @@ assert firstSpillChild.from() < splitChild.from(); } // iterate all blocks where the interval has use positions - for (AbstractBlock<?> splitBlock : blocksForInterval(splitChild)) { + for (AbstractBlockBase<?> splitBlock : blocksForInterval(splitChild)) { if (dominates(defBlock, splitBlock)) { Debug.log("Split interval %s, block %s", splitChild, splitBlock); if (spillBlock == null) { @@ -1858,7 +1858,7 @@ */ assert firstSpillChild != null; if (!defBlock.equals(spillBlock) && spillBlock.equals(blockForId(firstSpillChild.from()))) { - AbstractBlock<?> dom = spillBlock.getDominator(); + AbstractBlockBase<?> dom = spillBlock.getDominator(); Debug.log("Spill block (%s) is the beginning of a spill child -> use dominator (%s)", spillBlock, dom); spillBlock = dom; } @@ -1910,20 +1910,20 @@ } /** - * Iterate over all {@link AbstractBlock blocks} of an interval. + * Iterate over all {@link AbstractBlockBase blocks} of an interval. */ - private class IntervalBlockIterator implements Iterator<AbstractBlock<?>> { + private class IntervalBlockIterator implements Iterator<AbstractBlockBase<?>> { Range range; - AbstractBlock<?> block; + AbstractBlockBase<?> block; public IntervalBlockIterator(Interval interval) { range = interval.first(); block = blockForId(range.from); } - public AbstractBlock<?> next() { - AbstractBlock<?> currentBlock = block; + public AbstractBlockBase<?> next() { + AbstractBlockBase<?> currentBlock = block; int nextBlockIndex = block.getLinearScanNumber() + 1; if (nextBlockIndex < sortedBlocks.size()) { block = sortedBlocks.get(nextBlockIndex); @@ -1946,17 +1946,17 @@ } } - private Iterable<AbstractBlock<?>> blocksForInterval(Interval interval) { - return new Iterable<AbstractBlock<?>>() { - public Iterator<AbstractBlock<?>> iterator() { + private Iterable<AbstractBlockBase<?>> blocksForInterval(Interval interval) { + return new Iterable<AbstractBlockBase<?>>() { + public Iterator<AbstractBlockBase<?>> iterator() { return new IntervalBlockIterator(interval); } }; } - private static AbstractBlock<?> moveSpillOutOfLoop(AbstractBlock<?> defBlock, AbstractBlock<?> spillBlock) { + private static AbstractBlockBase<?> moveSpillOutOfLoop(AbstractBlockBase<?> defBlock, AbstractBlockBase<?> spillBlock) { int defLoopDepth = defBlock.getLoopDepth(); - for (AbstractBlock<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) { + for (AbstractBlockBase<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) { assert block != null : "spill block not dominated by definition block?"; if (block.getLoopDepth() <= defLoopDepth) { assert block.getLoopDepth() == defLoopDepth : "Cannot spill an interval outside of the loop where it is defined!"; @@ -1977,7 +1977,7 @@ try (Indent indent2 = Debug.logAndIndent("Basic Blocks")) { for (int i = 0; i < blockCount(); i++) { - AbstractBlock<?> block = blockAt(i); + AbstractBlockBase<?> block = blockAt(i); Debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop()); } } @@ -2110,7 +2110,7 @@ otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1); IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals); - for (AbstractBlock<?> block : sortedBlocks) { + for (AbstractBlockBase<?> block : sortedBlocks) { List<LIRInstruction> instructions = ir.getLIRforBlock(block); for (int j = 0; j < instructions.size(); j++) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java Mon Feb 23 20:13:29 2015 +0100 @@ -33,7 +33,7 @@ public final class LinearScanPhase extends AllocationPhase { @Override - protected <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) { + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) { new LinearScan(target, lirGenRes, spillMoveFactory).allocate(); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanWalker.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanWalker.java Mon Feb 23 20:13:29 2015 +0100 @@ -63,11 +63,11 @@ return allocator.blockCount(); } - AbstractBlock<?> blockAt(int idx) { + AbstractBlockBase<?> blockAt(int idx) { return allocator.blockAt(idx); } - AbstractBlock<?> blockOfOpWithId(int opId) { + AbstractBlockBase<?> blockOfOpWithId(int opId) { return allocator.blockForId(opId); } @@ -239,7 +239,7 @@ // optimized away later in assignRegNums int opId = (operandId + 1) & ~1; - AbstractBlock<?> opBlock = allocator.blockForId(opId); + AbstractBlockBase<?> opBlock = allocator.blockForId(opId); assert opId > 0 && allocator.blockForId(opId - 2) == opBlock : "cannot insert move at block boundary"; // calculate index of instruction inside instruction list of current block @@ -263,7 +263,7 @@ moveResolver.addMapping(srcIt, dstIt); } - int findOptimalSplitPos(AbstractBlock<?> minBlock, AbstractBlock<?> maxBlock, int maxSplitPos) { + int findOptimalSplitPos(AbstractBlockBase<?> minBlock, AbstractBlockBase<?> maxBlock, int maxSplitPos) { int fromBlockNr = minBlock.getLinearScanNumber(); int toBlockNr = maxBlock.getLinearScanNumber(); @@ -280,7 +280,7 @@ int minLoopDepth = maxBlock.getLoopDepth(); for (int i = toBlockNr - 1; i >= fromBlockNr; i--) { - AbstractBlock<?> cur = blockAt(i); + AbstractBlockBase<?> cur = blockAt(i); if (cur.getLoopDepth() < minLoopDepth) { // block with lower loop-depth found . split at the end of this block @@ -308,13 +308,13 @@ // beginning of a block, then minSplitPos is also a possible split position. // Use the block before as minBlock, because then minBlock.lastLirInstructionId() + 2 == // minSplitPos - AbstractBlock<?> minBlock = allocator.blockForId(minSplitPos - 1); + AbstractBlockBase<?> minBlock = allocator.blockForId(minSplitPos - 1); // reason for using maxSplitPos - 1: otherwise there would be an assert on failure // when an interval ends at the end of the last block of the method // (in this case, maxSplitPos == allocator().maxLirOpId() + 2, and there is no // block at this opId) - AbstractBlock<?> maxBlock = allocator.blockForId(maxSplitPos - 1); + AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSplitPos - 1); assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order"; if (minBlock == maxBlock) { @@ -352,7 +352,7 @@ // Desired result: uses tagged as shouldHaveRegister inside a loop cause // a reloading // of the interval (normally, only mustHaveRegister causes a reloading) - AbstractBlock<?> loopBlock = allocator.blockForId(loopEndPos); + AbstractBlockBase<?> loopBlock = allocator.blockForId(loopEndPos); Debug.log("interval is used in loop that ends in block B%d, so trying to move maxBlock back from B%d to B%d", loopBlock.getId(), maxBlock.getId(), loopBlock.getId()); assert loopBlock != minBlock : "loopBlock and minBlock must be different because block boundary is needed between";
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LocationMarker.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LocationMarker.java Mon Feb 23 20:13:29 2015 +0100 @@ -53,7 +53,7 @@ } @Override - protected <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) { + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) { new Marker(lirGenRes.getLIR(), lirGenRes.getFrameMap()).build(); } @@ -73,19 +73,19 @@ } private void build() { - Deque<AbstractBlock<?>> worklist = new ArrayDeque<>(); + Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(); for (int i = lir.getControlFlowGraph().getBlocks().size() - 1; i >= 0; i--) { worklist.add(lir.getControlFlowGraph().getBlocks().get(i)); } - for (AbstractBlock<?> block : lir.getControlFlowGraph().getBlocks()) { + for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) { liveInMap.put(block, frameMap.initReferenceMap(true)); } while (!worklist.isEmpty()) { - AbstractBlock<?> block = worklist.poll(); + AbstractBlockBase<?> block = worklist.poll(); processBlock(block, worklist); } // finish states - for (AbstractBlock<?> block : lir.getControlFlowGraph().getBlocks()) { + for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) { List<LIRInstruction> instructions = lir.getLIRforBlock(block); for (int i = instructions.size() - 1; i >= 0; i--) { LIRInstruction inst = instructions.get(i); @@ -98,7 +98,7 @@ /** * Merge outSet with in-set of successors. */ - private boolean updateOutBlock(AbstractBlock<?> block) { + private boolean updateOutBlock(AbstractBlockBase<?> block) { ReferenceMap union = frameMap.initReferenceMap(true); block.getSuccessors().forEach(succ -> union.updateUnion(liveInMap.get(succ))); ReferenceMap outSet = liveOutMap.get(block); @@ -110,7 +110,7 @@ return false; } - private void processBlock(AbstractBlock<?> block, Deque<AbstractBlock<?>> worklist) { + private void processBlock(AbstractBlockBase<?> block, Deque<AbstractBlockBase<?>> worklist) { if (updateOutBlock(block)) { try (Indent indent = Debug.logAndIndent("handle block %s", block)) { BlockClosure closure = new BlockClosure(liveOutMap.get(block).clone());
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/OptimizingLinearScanWalker.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/OptimizingLinearScanWalker.java Mon Feb 23 20:13:29 2015 +0100 @@ -71,14 +71,14 @@ @Override void walk() { try (Scope s = Debug.scope("OptimizingLinearScanWalker")) { - for (AbstractBlock<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks) { optimizeBlock(block); } } super.walk(); } - private void optimizeBlock(AbstractBlock<?> block) { + private void optimizeBlock(AbstractBlockBase<?> block) { if (block.getPredecessorCount() == 1) { int nextBlock = allocator.getFirstLirInstructionId(block); try (Scope s1 = Debug.scope("LSRAOptimization")) { @@ -114,7 +114,7 @@ } } - private boolean optimize(int currentPos, AbstractBlock<?> currentBlock, Interval currentInterval, RegisterBinding binding) { + private boolean optimize(int currentPos, AbstractBlockBase<?> currentBlock, Interval currentInterval, RegisterBinding binding) { // BEGIN initialize and sanity checks assert currentBlock != null : "block must not be null"; assert currentInterval != null : "interval must not be null"; @@ -136,7 +136,7 @@ assert currentLocation != null : "active intervals must have a location assigned!"; // get predecessor stuff - AbstractBlock<?> predecessorBlock = currentBlock.getPredecessors().get(0); + AbstractBlockBase<?> predecessorBlock = currentBlock.getPredecessors().get(0); int predEndId = allocator.getLastLirInstructionId(predecessorBlock); Interval predecessorInterval = currentInterval.getIntervalCoveringOpId(predEndId); assert predecessorInterval != null : "variable not live at the end of the only predecessor! " + predecessorBlock + " -> " + currentBlock + " interval: " + currentInterval;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/RegisterVerifier.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/RegisterVerifier.java Mon Feb 23 20:13:29 2015 +0100 @@ -41,7 +41,7 @@ final class RegisterVerifier { LinearScan allocator; - List<AbstractBlock<?>> workList; // all blocks that must be processed + List<AbstractBlockBase<?>> workList; // all blocks that must be processed ArrayMap<Interval[]> savedStates; // saved information of previous check // simplified access to methods of LinearScan @@ -55,15 +55,15 @@ } // accessors - Interval[] stateForBlock(AbstractBlock<?> block) { + Interval[] stateForBlock(AbstractBlockBase<?> block) { return savedStates.get(block.getId()); } - void setStateForBlock(AbstractBlock<?> block, Interval[] savedState) { + void setStateForBlock(AbstractBlockBase<?> block, Interval[] savedState) { savedStates.put(block.getId(), savedState); } - void addToWorkList(AbstractBlock<?> block) { + void addToWorkList(AbstractBlockBase<?> block) { if (!workList.contains(block)) { workList.add(block); } @@ -76,7 +76,7 @@ } - void verify(AbstractBlock<?> start) { + void verify(AbstractBlockBase<?> start) { // setup input registers (method arguments) for first block Interval[] inputState = new Interval[stateSize()]; setStateForBlock(start, inputState); @@ -84,14 +84,14 @@ // main loop for verification do { - AbstractBlock<?> block = workList.get(0); + AbstractBlockBase<?> block = workList.get(0); workList.remove(0); processBlock(block); } while (!workList.isEmpty()); } - private void processBlock(AbstractBlock<?> block) { + private void processBlock(AbstractBlockBase<?> block) { try (Indent indent = Debug.logAndIndent("processBlock B%d", block.getId())) { // must copy state because it is modified Interval[] inputState = copy(stateForBlock(block)); @@ -110,13 +110,13 @@ processOperations(allocator.ir.getLIRforBlock(block), inputState); // iterate all successors - for (AbstractBlock<?> succ : block.getSuccessors()) { + for (AbstractBlockBase<?> succ : block.getSuccessors()) { processSuccessor(succ, inputState); } } } - private void processSuccessor(AbstractBlock<?> block, Interval[] inputState) { + private void processSuccessor(AbstractBlockBase<?> block, Interval[] inputState) { Interval[] savedState = stateForBlock(block); if (savedState != null) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/asm/CompilationResultBuilder.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/asm/CompilationResultBuilder.java Mon Feb 23 20:13:29 2015 +0100 @@ -330,7 +330,7 @@ */ public boolean isSuccessorEdge(LabelRef edge) { assert lir != null; - List<? extends AbstractBlock<?>> order = lir.codeEmittingOrder(); + List<? extends AbstractBlockBase<?>> order = lir.codeEmittingOrder(); assert order.get(currentBlockIndex) == edge.getSourceBlock(); return currentBlockIndex < order.size() - 1 && order.get(currentBlockIndex + 1) == edge.getTargetBlock(); } @@ -344,7 +344,7 @@ this.lir = lir; this.currentBlockIndex = 0; frameContext.enter(this); - for (AbstractBlock<?> b : lir.codeEmittingOrder()) { + for (AbstractBlockBase<?> b : lir.codeEmittingOrder()) { emitBlock(b); currentBlockIndex++; } @@ -352,7 +352,7 @@ this.currentBlockIndex = 0; } - private void emitBlock(AbstractBlock<?> block) { + private void emitBlock(AbstractBlockBase<?> block) { if (Debug.isDumpEnabled()) { blockComment(String.format("block B%d %s", block.getId(), block.getLoop())); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/ConstantLoadOptimization.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/ConstantLoadOptimization.java Mon Feb 23 20:13:29 2015 +0100 @@ -57,7 +57,7 @@ } @Override - protected <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, LIRGeneratorTool lirGen) { + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, LIRGeneratorTool lirGen) { new Optimization(lirGenRes.getLIR(), lirGen).apply(); } @@ -135,7 +135,7 @@ assert !operand.equals(var) : "constant usage through variable in frame state " + var; } }; - for (AbstractBlock<?> block : lir.getControlFlowGraph().getBlocks()) { + for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) { for (LIRInstruction inst : lir.getLIRforBlock(block)) { // set instruction id to the index in the lir instruction list inst.visitEachState(stateConsumer); @@ -152,7 +152,7 @@ } private void addUsageToBlockMap(UseEntry entry) { - AbstractBlock<?> block = entry.getBlock(); + AbstractBlockBase<?> block = entry.getBlock(); List<UseEntry> list = blockMap.get(block); if (list == null) { list = new ArrayList<>(); @@ -164,7 +164,7 @@ /** * Collects def-use information for a {@code block}. */ - private void analyzeBlock(AbstractBlock<?> block) { + private void analyzeBlock(AbstractBlockBase<?> block) { try (Indent indent = Debug.logAndIndent("Block: %s", block)) { InstructionValueConsumer loadConsumer = (instruction, value, mode, flags) -> { @@ -267,17 +267,17 @@ Debug.dump(constTree, "ConstantTree for " + tree.getVariable()); } - private void createLoads(DefUseTree tree, ConstantTree constTree, AbstractBlock<?> startBlock) { - Deque<AbstractBlock<?>> worklist = new ArrayDeque<>(); + private void createLoads(DefUseTree tree, ConstantTree constTree, AbstractBlockBase<?> startBlock) { + Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(); worklist.add(startBlock); while (!worklist.isEmpty()) { - AbstractBlock<?> block = worklist.pollLast(); + AbstractBlockBase<?> block = worklist.pollLast(); if (constTree.get(Flags.CANDIDATE, block)) { constTree.set(Flags.MATERIALIZE, block); // create and insert load insertLoad(tree.getConstant(), tree.getVariable().getLIRKind(), block, constTree.getCost(block).getUsages()); } else { - for (AbstractBlock<?> dominated : block.getDominated()) { + for (AbstractBlockBase<?> dominated : block.getDominated()) { if (constTree.isMarked(dominated)) { worklist.addLast(dominated); } @@ -286,7 +286,7 @@ } } - private void insertLoad(JavaConstant constant, LIRKind kind, AbstractBlock<?> block, List<UseEntry> usages) { + private void insertLoad(JavaConstant constant, LIRKind kind, AbstractBlockBase<?> block, List<UseEntry> usages) { assert usages != null && usages.size() > 0 : String.format("No usages %s %s %s", constant, block, usages); // create variable Variable variable = lirGen.newVariable(kind); @@ -306,7 +306,7 @@ * Inserts the constant loads created in {@link #createConstantTree} and deletes the * original definition. */ - private void rewriteBlock(AbstractBlock<?> block) { + private void rewriteBlock(AbstractBlockBase<?> block) { // insert moves LIRInsertionBuffer buffer = insertionBuffers.get(block); if (buffer != null) { @@ -331,13 +331,13 @@ } private void deleteInstruction(DefUseTree tree) { - AbstractBlock<?> block = tree.getBlock(); + AbstractBlockBase<?> block = tree.getBlock(); LIRInstruction instruction = tree.getInstruction(); Debug.log("deleting instruction %s from block %s", instruction, block); lir.getLIRforBlock(block).set(instruction.id(), null); } - private LIRInsertionBuffer getInsertionBuffer(AbstractBlock<?> block) { + private LIRInsertionBuffer getInsertionBuffer(AbstractBlockBase<?> block) { LIRInsertionBuffer insertionBuffer = insertionBuffers.get(block); if (insertionBuffer == null) { insertionBuffer = new LIRInsertionBuffer();
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/ConstantTree.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/ConstantTree.java Mon Feb 23 20:13:29 2015 +0100 @@ -99,7 +99,7 @@ tree.forEach(u -> getOrInitList(u.getBlock()).add(u)); } - private List<UseEntry> getOrInitList(AbstractBlock<?> block) { + private List<UseEntry> getOrInitList(AbstractBlockBase<?> block) { List<UseEntry> list = blockMap.get(block); if (list == null) { list = new ArrayList<>(); @@ -108,7 +108,7 @@ return list; } - public List<UseEntry> getUsages(AbstractBlock<?> block) { + public List<UseEntry> getUsages(AbstractBlockBase<?> block) { List<UseEntry> list = blockMap.get(block); if (list == null) { return Collections.emptyList(); @@ -120,7 +120,7 @@ * Returns the cost object associated with {@code block}. If there is none, a new cost object is * created. */ - NodeCost getOrInitCost(AbstractBlock<?> block) { + NodeCost getOrInitCost(AbstractBlockBase<?> block) { NodeCost cost = getCost(block); if (cost == null) { cost = new NodeCost(block.probability(), blockMap.get(block), 1); @@ -145,7 +145,7 @@ } @Override - public void forEachPropertyPair(AbstractBlock<?> block, BiConsumer<String, String> action) { + public void forEachPropertyPair(AbstractBlockBase<?> block, BiConsumer<String, String> action) { if (get(Flags.SUBTREE, block) && (block.getDominator() == null || !get(Flags.SUBTREE, block.getDominator()))) { action.accept("hasDefinition", "true"); } @@ -156,7 +156,7 @@ return stream(Flags.SUBTREE).count(); } - public AbstractBlock<?> getStartBlock() { + public AbstractBlockBase<?> getStartBlock() { return stream(Flags.SUBTREE).findFirst().get(); } @@ -164,15 +164,15 @@ stream(Flags.USAGE).forEach(block -> setDominatorPath(Flags.SUBTREE, block)); } - public boolean isMarked(AbstractBlock<?> block) { + public boolean isMarked(AbstractBlockBase<?> block) { return get(Flags.SUBTREE, block); } - public boolean isLeafBlock(AbstractBlock<?> block) { + public boolean isLeafBlock(AbstractBlockBase<?> block) { return block.getDominated().stream().noneMatch(this::isMarked); } - public void setSolution(AbstractBlock<?> block) { + public void setSolution(AbstractBlockBase<?> block) { set(Flags.MATERIALIZE, block); } @@ -180,7 +180,7 @@ return getBlocks().size(); } - public void traverseTreeWhileTrue(AbstractBlock<?> block, Predicate<AbstractBlock<?>> action) { + public void traverseTreeWhileTrue(AbstractBlockBase<?> block, Predicate<AbstractBlockBase<?>> action) { assert block != null : "block must not be null!"; if (action.test(block)) { block.getDominated().stream().filter(this::isMarked).forEach(dominated -> traverseTreeWhileTrue(dominated, action));
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/ConstantTreeAnalyzer.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/ConstantTreeAnalyzer.java Mon Feb 23 20:13:29 2015 +0100 @@ -37,7 +37,7 @@ private final ConstantTree tree; private final BitSet visited; - public static NodeCost analyze(ConstantTree tree, AbstractBlock<?> startBlock) { + public static NodeCost analyze(ConstantTree tree, AbstractBlockBase<?> startBlock) { try (Scope s = Debug.scope("ConstantTreeAnalyzer")) { ConstantTreeAnalyzer analyzer = new ConstantTreeAnalyzer(tree); analyzer.analyzeBlocks(startBlock); @@ -60,11 +60,11 @@ * * @param startBlock The start block of the dominator subtree. */ - private void analyzeBlocks(AbstractBlock<?> startBlock) { - Deque<AbstractBlock<?>> worklist = new ArrayDeque<>(); + private void analyzeBlocks(AbstractBlockBase<?> startBlock) { + Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(); worklist.offerLast(startBlock); while (!worklist.isEmpty()) { - AbstractBlock<?> block = worklist.pollLast(); + AbstractBlockBase<?> block = worklist.pollLast(); try (Indent i = Debug.logAndIndent(3, "analyze: %s", block)) { assert block != null : "worklist is empty!"; assert isMarked(block) : "Block not part of the dominator tree: " + block; @@ -79,7 +79,7 @@ // if not yet visited (and not a leaf block) process all children first! Debug.log(3, "not marked"); worklist.offerLast(block); - List<? extends AbstractBlock<?>> children = block.getDominated(); + List<? extends AbstractBlockBase<?>> children = block.getDominated(); children.forEach(child -> filteredPush(worklist, child)); visited.set(block.getId()); } else { @@ -97,15 +97,15 @@ * * @param block The block to be processed. */ - private void process(AbstractBlock<?> block) { + private void process(AbstractBlockBase<?> block) { List<UseEntry> usages = new ArrayList<>(); double bestCost = 0; int numMat = 0; - List<? extends AbstractBlock<?>> children = block.getDominated(); + List<? extends AbstractBlockBase<?>> children = block.getDominated(); assert children.stream().anyMatch(this::isMarked) : "no children? should have called leafCost(): " + block; // collect children costs - for (AbstractBlock<?> child : children) { + for (AbstractBlockBase<?> child : children) { if (isMarked(child)) { NodeCost childCost = tree.getCost(child); assert childCost != null : "Child with null cost? block: " + child; @@ -151,23 +151,23 @@ return probabilityBlock * Math.pow(0.9, numMat - 1) < probabilityChildren; } - private void filteredPush(Deque<AbstractBlock<?>> worklist, AbstractBlock<?> block) { + private void filteredPush(Deque<AbstractBlockBase<?>> worklist, AbstractBlockBase<?> block) { if (isMarked(block)) { Debug.log(3, "adding %s to the worklist", block); worklist.offerLast(block); } } - private void leafCost(AbstractBlock<?> block) { + private void leafCost(AbstractBlockBase<?> block) { tree.set(Flags.CANDIDATE, block); tree.getOrInitCost(block); } - private boolean isMarked(AbstractBlock<?> block) { + private boolean isMarked(AbstractBlockBase<?> block) { return tree.isMarked(block); } - private boolean isLeafBlock(AbstractBlock<?> block) { + private boolean isLeafBlock(AbstractBlockBase<?> block) { return tree.isLeafBlock(block); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/DefUseTree.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/DefUseTree.java Mon Feb 23 20:13:29 2015 +0100 @@ -35,10 +35,10 @@ */ class DefUseTree { private final LIRInstruction instruction; - private final AbstractBlock<?> block; + private final AbstractBlockBase<?> block; private final List<UseEntry> uses; - public DefUseTree(LIRInstruction instruction, AbstractBlock<?> block) { + public DefUseTree(LIRInstruction instruction, AbstractBlockBase<?> block) { assert instruction instanceof MoveOp : "Not a MoveOp: " + instruction; this.instruction = instruction; this.block = block; @@ -57,7 +57,7 @@ return instruction; } - public AbstractBlock<?> getBlock() { + public AbstractBlockBase<?> getBlock() { return block; } @@ -66,7 +66,7 @@ return "DefUseTree [" + instruction + "|" + block + "," + uses + "]"; } - public void addUsage(AbstractBlock<?> b, LIRInstruction inst, ValuePosition position) { + public void addUsage(AbstractBlockBase<?> b, LIRInstruction inst, ValuePosition position) { uses.add(new UseEntry(b, inst, position)); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/UseEntry.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/UseEntry.java Mon Feb 23 20:13:29 2015 +0100 @@ -31,11 +31,11 @@ */ class UseEntry { - private final AbstractBlock<?> block; + private final AbstractBlockBase<?> block; private final LIRInstruction instruction; private final ValuePosition position; - public UseEntry(AbstractBlock<?> block, LIRInstruction instruction, ValuePosition position) { + public UseEntry(AbstractBlockBase<?> block, LIRInstruction instruction, ValuePosition position) { this.block = block; this.instruction = instruction; this.position = position; @@ -45,7 +45,7 @@ return instruction; } - public AbstractBlock<?> getBlock() { + public AbstractBlockBase<?> getBlock() { return block; }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderImpl.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderImpl.java Mon Feb 23 20:13:29 2015 +0100 @@ -117,7 +117,7 @@ InstructionValueConsumer verifySlots = (LIRInstruction op, Value value, OperandMode mode, EnumSet<OperandFlag> flags) -> { assert !isVirtualStackSlot(value) : String.format("Instruction %s contains a virtual stack slot %s", op, value); }; - for (AbstractBlock<?> block : lir.getControlFlowGraph().getBlocks()) { + for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) { lir.getLIRforBlock(block).forEach(op -> { op.visitEachInput(verifySlots); op.visitEachAlive(verifySlots);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerator.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerator.java Mon Feb 23 20:13:29 2015 +0100 @@ -60,7 +60,7 @@ private final CodeGenProviders providers; private final CallingConvention cc; - private AbstractBlock<?> currentBlock; + private AbstractBlockBase<?> currentBlock; private LIRGenerationResult res; @@ -186,7 +186,7 @@ res.getLIR().getLIRforBlock(currentBlock).add(op); } - public boolean hasBlockEnd(AbstractBlock<?> block) { + public boolean hasBlockEnd(AbstractBlockBase<?> block) { List<LIRInstruction> ops = getResult().getLIR().getLIRforBlock(block); if (ops.size() == 0) { return false; @@ -194,7 +194,7 @@ return ops.get(ops.size() - 1) instanceof BlockEndOp; } - public final void doBlockStart(AbstractBlock<?> block) { + public final void doBlockStart(AbstractBlockBase<?> block) { if (Options.PrintIRWithLIR.getValue()) { TTY.print(block.toString()); } @@ -212,7 +212,7 @@ } } - public final void doBlockEnd(AbstractBlock<?> block) { + public final void doBlockEnd(AbstractBlockBase<?> block) { if (Options.TraceLIRGeneratorLevel.getValue() >= 1) { TTY.println("END Generating LIR for block B" + block.getId()); @@ -379,7 +379,7 @@ } } - public AbstractBlock<?> getCurrentBlock() { + public AbstractBlockBase<?> getCurrentBlock() { return currentBlock; }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGeneratorTool.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGeneratorTool.java Mon Feb 23 20:13:29 2015 +0100 @@ -47,17 +47,17 @@ ForeignCallsProvider getForeignCalls(); - AbstractBlock<?> getCurrentBlock(); + AbstractBlockBase<?> getCurrentBlock(); LIRGenerationResult getResult(); + boolean hasBlockEnd(AbstractBlockBase<?> block); + SpillMoveFactory getSpillMoveFactory(); - boolean hasBlockEnd(AbstractBlock<?> block); + void doBlockStart(AbstractBlockBase<?> block); - void doBlockStart(AbstractBlock<?> block); - - void doBlockEnd(AbstractBlock<?> block); + void doBlockEnd(AbstractBlockBase<?> block); Value emitLoadConstant(LIRKind kind, Constant constant);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/AllocationPhase.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/AllocationPhase.java Mon Feb 23 20:13:29 2015 +0100 @@ -40,11 +40,11 @@ } @Override - protected final <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, AllocationContext context) { + protected final <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, AllocationContext context) { run(target, lirGenRes, codeEmittingOrder, linearScanOrder, context.spillMoveFactory); } - protected abstract <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, + protected abstract <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/LIRPhase.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/LIRPhase.java Mon Feb 23 20:13:29 2015 +0100 @@ -73,11 +73,11 @@ memUseTracker = Debug.memUseTracker("LIRPhaseMemUse_%s", getClass()); } - public final <B extends AbstractBlock<B>> void apply(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, C context) { + public final <B extends AbstractBlockBase<B>> void apply(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, C context) { apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, true); } - public final <B extends AbstractBlock<B>> void apply(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, C context, boolean dumpLIR) { + public final <B extends AbstractBlockBase<B>> void apply(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, C context, boolean dumpLIR) { try (TimerCloseable a = timer.start(); Scope s = Debug.scope(getName(), this); Closeable c = memUseTracker.start()) { run(target, lirGenRes, codeEmittingOrder, linearScanOrder, context); if (dumpLIR && Debug.isDumpEnabled(PHASE_DUMP_LEVEL)) { @@ -88,7 +88,7 @@ } } - protected abstract <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, C context); + protected abstract <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, C context); protected CharSequence createName() { String className = LIRPhase.this.getClass().getName();
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/LIRPhaseSuite.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/LIRPhaseSuite.java Mon Feb 23 20:13:29 2015 +0100 @@ -69,7 +69,7 @@ } @Override - protected <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, C context) { + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, C context) { for (LIRPhase<C> phase : phases) { phase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/PostAllocationOptimizationPhase.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/PostAllocationOptimizationPhase.java Mon Feb 23 20:13:29 2015 +0100 @@ -34,11 +34,11 @@ } @Override - protected final <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, + protected final <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, PostAllocationOptimizationContext context) { run(target, lirGenRes, codeEmittingOrder, linearScanOrder); } - protected abstract <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder); + protected abstract <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/PreAllocationOptimizationPhase.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/PreAllocationOptimizationPhase.java Mon Feb 23 20:13:29 2015 +0100 @@ -40,11 +40,11 @@ } @Override - protected final <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, + protected final <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, PreAllocationOptimizationContext context) { run(target, lirGenRes, codeEmittingOrder, linearScanOrder, context.lirGen); } - protected abstract <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, LIRGeneratorTool lirGen); + protected abstract <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, LIRGeneratorTool lirGen); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/FixPointIntervalBuilder.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/FixPointIntervalBuilder.java Mon Feb 23 20:13:29 2015 +0100 @@ -65,15 +65,15 @@ * virtual stack slots. */ Set<LIRInstruction> build() { - Deque<AbstractBlock<?>> worklist = new ArrayDeque<>(); + Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(); for (int i = lir.getControlFlowGraph().getBlocks().size() - 1; i >= 0; i--) { worklist.add(lir.getControlFlowGraph().getBlocks().get(i)); } - for (AbstractBlock<?> block : lir.getControlFlowGraph().getBlocks()) { + for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) { liveInMap.put(block, new BitSet(stackSlotMap.length)); } while (!worklist.isEmpty()) { - AbstractBlock<?> block = worklist.poll(); + AbstractBlockBase<?> block = worklist.poll(); processBlock(block, worklist); } return usePos; @@ -82,7 +82,7 @@ /** * Merge outSet with in-set of successors. */ - private boolean updateOutBlock(AbstractBlock<?> block) { + private boolean updateOutBlock(AbstractBlockBase<?> block) { BitSet union = new BitSet(stackSlotMap.length); block.getSuccessors().forEach(succ -> union.or(liveInMap.get(succ))); BitSet outSet = liveOutMap.get(block); @@ -94,7 +94,7 @@ return false; } - private void processBlock(AbstractBlock<?> block, Deque<AbstractBlock<?>> worklist) { + private void processBlock(AbstractBlockBase<?> block, Deque<AbstractBlockBase<?>> worklist) { if (updateOutBlock(block)) { try (Indent indent = Debug.logAndIndent("handle block %s", block)) { List<LIRInstruction> instructions = lir.getLIRforBlock(block);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java Mon Feb 23 20:13:29 2015 +0100 @@ -69,7 +69,7 @@ private static final DebugTimer AssignSlotsTimer = Debug.timer("LSStackSlotAllocator[AssignSlots]"); @Override - protected <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) { + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) { lirGenRes.buildFrameMap(this); } @@ -85,7 +85,7 @@ private final StackInterval[] stackSlotMap; private final PriorityQueue<StackInterval> unhandled; private final PriorityQueue<StackInterval> active; - private final List<? extends AbstractBlock<?>> sortedBlocks; + private final List<? extends AbstractBlockBase<?>> sortedBlocks; private final int maxOpId; private Allocator(LIR lir, FrameMapBuilderTool frameMapBuilder) { @@ -150,10 +150,10 @@ * * @return The id of the last operation. */ - private static int numberInstructions(LIR lir, List<? extends AbstractBlock<?>> sortedBlocks) { + private static int numberInstructions(LIR lir, List<? extends AbstractBlockBase<?>> sortedBlocks) { int opId = 0; int index = 0; - for (AbstractBlock<?> block : sortedBlocks) { + for (AbstractBlockBase<?> block : sortedBlocks) { List<LIRInstruction> instructions = lir.getLIRforBlock(block);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/SimpleStackSlotAllocator.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/SimpleStackSlotAllocator.java Mon Feb 23 20:13:29 2015 +0100 @@ -40,7 +40,7 @@ public class SimpleStackSlotAllocator extends AllocationPhase implements StackSlotAllocator { @Override - protected <B extends AbstractBlock<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) { + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) { lirGenRes.buildFrameMap(this); } @@ -76,7 +76,7 @@ } return value; }; - for (AbstractBlock<?> block : res.getLIR().getControlFlowGraph().getBlocks()) { + for (AbstractBlockBase<?> block : res.getLIR().getControlFlowGraph().getBlocks()) { try (Indent indent0 = Debug.logAndIndent("block: %s", block)) { for (LIRInstruction inst : res.getLIR().getLIRforBlock(block)) { try (Indent indent1 = Debug.logAndIndent("Inst: %d: %s", inst.id(), inst)) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Mon Feb 23 20:13:29 2015 +0100 @@ -30,6 +30,7 @@ public final class Block extends AbstractBlockBase<Block> { + public static final int DISTANCED_DOMINATOR_CACHE = 5; protected final AbstractBeginNode beginNode; protected FixedNode endNode; @@ -38,6 +39,7 @@ protected Loop<Block> loop; protected Block postdominator; + protected Block distancedDominatorCache; protected Block(AbstractBeginNode node) { this.beginNode = node; @@ -51,6 +53,7 @@ return endNode; } + @Override public Loop<Block> getLoop() { return loop; } @@ -59,18 +62,22 @@ this.loop = loop; } + @Override public int getLoopDepth() { return loop == null ? 0 : loop.getDepth(); } + @Override public boolean isLoopHeader() { return getBeginNode() instanceof LoopBeginNode; } + @Override public boolean isLoopEnd() { return getEndNode() instanceof LoopEndNode; } + @Override public boolean isExceptionEntry() { Node predecessor = getBeginNode().predecessor(); return predecessor != null && predecessor instanceof InvokeWithExceptionNode && getBeginNode() == ((InvokeWithExceptionNode) predecessor).exceptionEdge(); @@ -97,6 +104,7 @@ return b; } + @Override public Block getPostdominator() { return postdominator; } @@ -159,6 +167,7 @@ return "B" + id; } + @Override public double probability() { return probability; } @@ -167,4 +176,31 @@ assert probability >= 0 && Double.isFinite(probability); this.probability = probability; } + + public Block getDistancedDominatorCache() { + Block result = this.distancedDominatorCache; + if (result == null) { + Block current = this; + for (int i = 0; i < DISTANCED_DOMINATOR_CACHE; ++i) { + current = current.getDominator(); + } + distancedDominatorCache = current; + return current; + } else { + return result; + } + } + + @Override + public Block getDominator(int distance) { + Block result = this; + int i = 0; + for (; i < distance - (DISTANCED_DOMINATOR_CACHE - 1); i += DISTANCED_DOMINATOR_CACHE) { + result = result.getDistancedDominatorCache(); + } + for (; i < distance; ++i) { + result = result.getDominator(); + } + return result; + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java Mon Feb 23 20:13:29 2015 +0100 @@ -112,13 +112,16 @@ return FLOATING; } - public static void propagateKill(Node node) { + private static void propagateKill(Node node) { if (node != null && node.isAlive()) { - node.unsafeDelete(); + node.markDeleted(); - node.acceptInputs(in -> { - if (in.isAlive() && in.hasNoUsages() && !(in instanceof FixedNode)) { - killWithUnusedFloatingInputs(in); + node.acceptInputs((n, in) -> { + if (in.isAlive()) { + in.removeUsage(n); + if (in.hasNoUsages() && !(in instanceof FixedNode)) { + killWithUnusedFloatingInputs(in); + } } });
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CanonicalizerPhase.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CanonicalizerPhase.java Mon Feb 23 20:13:29 2015 +0100 @@ -311,9 +311,6 @@ if (canonical != null && !canonical.isAlive()) { assert !canonical.isDeleted(); canonical = graph.addOrUniqueWithInputs(canonical); - if (canonical == node) { - graph.addOrUniqueWithInputs(newCanonical); - } } if (node instanceof FloatingNode) { if (canonical == null) {
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DeadCodeEliminationPhase.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DeadCodeEliminationPhase.java Mon Feb 23 20:13:29 2015 +0100 @@ -24,6 +24,8 @@ import static com.oracle.graal.phases.common.DeadCodeEliminationPhase.Options.*; +import java.util.function.*; + import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; @@ -70,93 +72,51 @@ if (optional && ReduceDCE.getValue()) { return; } + NodeFlood flood = graph.createNodeFlood(); - + int totalNodeCount = graph.getNodeCount(); flood.add(graph.start()); - iterateSuccessors(flood); - disconnectCFGNodes(flood, graph); - iterateInputs(flood, graph); + iterateSuccessorsAndInputs(flood); + int totalMarkedCount = flood.getTotalMarkedCount(); + if (totalNodeCount == totalMarkedCount) { + // All nodes are live => nothing more to do. + return; + } else { + // Some nodes are not marked alive and therefore dead => proceed. + assert totalNodeCount > totalMarkedCount; + } + deleteNodes(flood, graph); - - // remove chained Merges - for (AbstractMergeNode merge : graph.getNodes(AbstractMergeNode.TYPE)) { - if (merge.forwardEndCount() == 1 && !(merge instanceof LoopBeginNode)) { - graph.reduceTrivialMerge(merge); - } - } } - private static void iterateSuccessors(NodeFlood flood) { + private static void iterateSuccessorsAndInputs(NodeFlood flood) { + BiConsumer<Node, Node> consumer = (n, succ) -> { + flood.add(succ); + }; for (Node current : flood) { if (current instanceof AbstractEndNode) { AbstractEndNode end = (AbstractEndNode) current; flood.add(end.merge()); } else { - for (Node successor : current.successors()) { - flood.add(successor); - } - } - } - } - - private static void disconnectCFGNodes(NodeFlood flood, StructuredGraph graph) { - for (AbstractEndNode node : graph.getNodes(AbstractEndNode.TYPE)) { - if (!flood.isMarked(node)) { - AbstractMergeNode merge = node.merge(); - if (merge != null && flood.isMarked(merge)) { - // We are a dead end node leading to a live merge. - merge.removeEnd(node); - } - } - } - for (LoopBeginNode loop : graph.getNodes(LoopBeginNode.TYPE)) { - if (flood.isMarked(loop)) { - boolean reachable = false; - for (LoopEndNode end : loop.loopEnds()) { - if (flood.isMarked(end)) { - reachable = true; - break; - } - } - if (!reachable) { - Debug.log("Removing loop with unreachable end: %s", loop); - for (LoopEndNode end : loop.loopEnds().snapshot()) { - loop.removeEnd(end); - } - graph.reduceDegenerateLoopBegin(loop); - } + current.acceptSuccessors(consumer); + current.acceptInputs(consumer); } } } private static void deleteNodes(NodeFlood flood, StructuredGraph graph) { + BiConsumer<Node, Node> consumer = (n, input) -> { + if (input.isAlive() && flood.isMarked(input)) { + input.removeUsage(n); + } + }; + for (Node node : graph.getNodes()) { if (!flood.isMarked(node)) { - node.clearInputs(); - node.clearSuccessors(); - } - } - for (Node node : graph.getNodes()) { - if (!flood.isMarked(node)) { + node.markDeleted(); + node.acceptInputs(consumer); metricNodesRemoved.increment(); - node.safeDelete(); } } } - - private static void iterateInputs(NodeFlood flood, StructuredGraph graph) { - for (Node node : graph.getNodes()) { - if (flood.isMarked(node)) { - for (Node input : node.inputs()) { - flood.add(input); - } - } - } - for (Node current : flood) { - for (Node input : current.inputs()) { - flood.add(input); - } - } - } - }
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FloatingReadPhase.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FloatingReadPhase.java Mon Feb 23 20:13:29 2015 +0100 @@ -45,7 +45,6 @@ private boolean createFloatingReads; private boolean createMemoryMapNodes; - private boolean updateExistingPhis; public static class MemoryMapImpl implements MemoryMap { @@ -90,7 +89,7 @@ } public FloatingReadPhase() { - this(true, false, false); + this(true, false); } /** @@ -99,13 +98,10 @@ * {@link FloatingReadNode}s) where possible * @param createMemoryMapNodes a {@link MemoryMapNode} will be created for each return if this * is true - * @param updateExistingPhis if true, then existing {@link MemoryPhiNode}s in the graph will be - * updated */ - public FloatingReadPhase(boolean createFloatingReads, boolean createMemoryMapNodes, boolean updateExistingPhis) { + public FloatingReadPhase(boolean createFloatingReads, boolean createMemoryMapNodes) { this.createFloatingReads = createFloatingReads; this.createMemoryMapNodes = createMemoryMapNodes; - this.updateExistingPhis = updateExistingPhis; } /** @@ -135,7 +131,7 @@ ReentrantNodeIterator.apply(new CollectMemoryCheckpointsClosure(modifiedInLoops), graph.start(), CollectionsFactory.newSet()); HashSetNodeEventListener listener = new HashSetNodeEventListener(EnumSet.of(NODE_ADDED, ZERO_USAGES)); try (NodeEventScope nes = graph.trackNodeEvents(listener)) { - ReentrantNodeIterator.apply(new FloatingReadClosure(modifiedInLoops, createFloatingReads, createMemoryMapNodes, updateExistingPhis), graph.start(), new MemoryMapImpl(graph.start())); + ReentrantNodeIterator.apply(new FloatingReadClosure(modifiedInLoops, createFloatingReads, createMemoryMapNodes), graph.start(), new MemoryMapImpl(graph.start())); } for (Node n : removeExternallyUsedNodes(listener.getNodes())) { @@ -150,7 +146,7 @@ } } - public static MemoryMapImpl mergeMemoryMaps(AbstractMergeNode merge, List<? extends MemoryMap> states, boolean updateExistingPhis) { + public static MemoryMapImpl mergeMemoryMaps(AbstractMergeNode merge, List<? extends MemoryMap> states) { MemoryMapImpl newState = new MemoryMapImpl(); Set<LocationIdentity> keys = CollectionsFactory.newSet(); @@ -159,17 +155,6 @@ } assert checkNoImmutableLocations(keys); - Map<LocationIdentity, MemoryPhiNode> existingPhis = null; - if (updateExistingPhis) { - for (MemoryPhiNode phi : merge.phis().filter(MemoryPhiNode.class)) { - if (existingPhis == null) { - existingPhis = CollectionsFactory.newMap(); - } - phi.values().clear(); - existingPhis.put(phi.getLocationIdentity(), phi); - } - } - for (LocationIdentity key : keys) { int mergedStatesCount = 0; boolean isPhi = false; @@ -184,10 +169,7 @@ } else if (merged == null) { merged = last; } else { - MemoryPhiNode phi = null; - if (existingPhis == null || (phi = existingPhis.remove(key)) == null) { - phi = merge.graph().addWithoutUnique(new MemoryPhiNode(merge, key)); - } + MemoryPhiNode phi = merge.graph().addWithoutUnique(new MemoryPhiNode(merge, key)); for (int j = 0; j < mergedStatesCount; j++) { phi.addInput(ValueNodeUtil.asNode(merged)); } @@ -200,11 +182,6 @@ } newState.lastMemorySnapshot.put(key, merged); } - if (existingPhis != null) { - for (Map.Entry<LocationIdentity, MemoryPhiNode> entry : existingPhis.entrySet()) { - entry.getValue().replaceAndDelete(newState.getLastLocationAccess(entry.getKey()).asNode()); - } - } return newState; } @@ -273,13 +250,11 @@ private final Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops; private boolean createFloatingReads; private boolean createMemoryMapNodes; - private boolean updateExistingPhis; - public FloatingReadClosure(Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops, boolean createFloatingReads, boolean createMemoryMapNodes, boolean updateExistingPhis) { + public FloatingReadClosure(Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops, boolean createFloatingReads, boolean createMemoryMapNodes) { this.modifiedInLoops = modifiedInLoops; this.createFloatingReads = createFloatingReads; this.createMemoryMapNodes = createMemoryMapNodes; - this.updateExistingPhis = updateExistingPhis; } @Override @@ -347,7 +322,7 @@ @Override protected MemoryMapImpl merge(AbstractMergeNode merge, List<MemoryMapImpl> states) { - return mergeMemoryMaps(merge, states, updateExistingPhis); + return mergeMemoryMaps(merge, states); } @Override @@ -378,24 +353,10 @@ Map<LocationIdentity, MemoryPhiNode> phis = CollectionsFactory.newMap(); - if (updateExistingPhis) { - for (MemoryPhiNode phi : loop.phis().filter(MemoryPhiNode.class).snapshot()) { - if (modifiedLocations.contains(phi.getLocationIdentity())) { - phi.values().clear(); - phi.addInput(ValueNodeUtil.asNode(initialState.getLastLocationAccess(phi.getLocationIdentity()))); - phis.put(phi.getLocationIdentity(), phi); - } else { - phi.replaceAndDelete(initialState.getLastLocationAccess(phi.getLocationIdentity()).asNode()); - } - } - } - for (LocationIdentity location : modifiedLocations) { - if (!updateExistingPhis || !phis.containsKey(location)) { - MemoryPhiNode phi = loop.graph().addWithoutUnique(new MemoryPhiNode(loop, location)); - phi.addInput(ValueNodeUtil.asNode(initialState.getLastLocationAccess(location))); - phis.put(location, phi); - } + MemoryPhiNode phi = loop.graph().addWithoutUnique(new MemoryPhiNode(loop, location)); + phi.addInput(ValueNodeUtil.asNode(initialState.getLastLocationAccess(location))); + phis.put(location, phi); } for (Map.Entry<LocationIdentity, MemoryPhiNode> entry : phis.entrySet()) { initialState.lastMemorySnapshot.put(entry.getKey(), entry.getValue());
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Mon Feb 23 20:13:29 2015 +0100 @@ -621,22 +621,21 @@ * @param earliestBlock */ private Block latestBlock(ValueNode node, SchedulingStrategy strategy, Block earliestBlock) { - CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(null); - ensureScheduledUsages(node, strategy); + Block block = null; for (Node usage : node.usages()) { - blocksForUsage(node, usage, cdbc, strategy); - if (cdbc.block == earliestBlock) { + block = blocksForUsage(node, usage, block, earliestBlock, strategy); + if (block == earliestBlock) { break; } } - assert assertLatestBlockResult(node, cdbc); - return cdbc.block; + assert assertLatestBlockResult(node, block); + return block; } - private boolean assertLatestBlockResult(ValueNode node, CommonDominatorBlockClosure cdbc) throws SchedulingError { - if (cdbc.block != null && !dominates(earliestBlock(node), cdbc.block)) { - throw new SchedulingError("failed to find correct latest schedule for %s. cdbc: %s, earliest: %s", node, cdbc.block, earliestBlock(node)); + private boolean assertLatestBlockResult(ValueNode node, Block block) throws SchedulingError { + if (block != null && !dominates(earliestBlock(node), block)) { + throw new SchedulingError("failed to find correct latest schedule for %s. cdbc: %s, earliest: %s", node, block, earliestBlock(node)); } return true; } @@ -671,41 +670,34 @@ if (earliest != null) { return earliest; } + return earliestBlockHelper(node, earliest); + } + + private Block earliestBlockHelper(Node node, Block earliestStart) throws SchedulingError { /* * All inputs must be in a dominating block, otherwise the graph cannot be scheduled. This * implies that the inputs' blocks have a total ordering via their dominance relation. So in * order to find the earliest block placement for this node we need to find the input block * that is dominated by all other input blocks. */ + Block earliest = earliestStart; if (node.predecessor() != null) { throw new SchedulingError(); } - for (Node input : node.inputs().nonNull()) { - assert input instanceof ValueNode; - Block inputEarliest; - if (input instanceof InvokeWithExceptionNode) { - inputEarliest = cfg.getNodeToBlock().get(((InvokeWithExceptionNode) input).next()); - } else { - inputEarliest = earliestBlock(input); - } - if (earliest == null) { - earliest = inputEarliest; - } else if (earliest != inputEarliest) { - // Find out whether earliest or inputEarliest is earlier. - Block a = earliest.getDominator(); - Block b = inputEarliest; - while (true) { - if (a == inputEarliest || b == null) { - // Nothing to change, the previous earliest block is still earliest. - break; - } else if (b == earliest || a == null) { - // New earliest is the earliest. - earliest = inputEarliest; - break; - } - a = a.getDominator(); - b = b.getDominator(); + for (Node input : node.inputs()) { + if (input != null) { + assert input instanceof ValueNode; + Block inputEarliest; + if (input instanceof InvokeWithExceptionNode) { + inputEarliest = cfg.getNodeToBlock().get(((InvokeWithExceptionNode) input).next()); + } else { + inputEarliest = earliestBlock(input); + } + if (earliest == null) { + earliest = inputEarliest; + } else if (earliest != inputEarliest) { + earliest = findEarlierBlock(earliest, inputEarliest); } } } @@ -716,6 +708,23 @@ return earliest; } + private static Block findEarlierBlock(Block earliest, Block inputEarliest) { + // Find out whether earliest or inputEarliest is earlier. + Block a = earliest.getDominator(); + Block b = inputEarliest; + while (true) { + if (a == inputEarliest || b == null) { + // Nothing to change, the previous earliest block is still earliest. + return earliest; + } else if (b == earliest || a == null) { + // New earliest is the earliest. + return inputEarliest; + } + a = a.getDominator(); + b = b.getDominator(); + } + } + /** * Schedules a node out of loop based on its earliest schedule. Note that this movement is only * valid if it's done for <b>every</b> other node in the schedule, otherwise this movement is @@ -748,11 +757,11 @@ * * @param node the node that needs to be scheduled * @param usage the usage whose blocks need to be considered - * @param closure the closure that will be called for each block + * @param earliestBlock */ - private void blocksForUsage(ValueNode node, Node usage, CommonDominatorBlockClosure closure, SchedulingStrategy strategy) { + private Block blocksForUsage(ValueNode node, Node usage, Block startCurrentBlock, Block earliestBlock, SchedulingStrategy strategy) { assert !(node instanceof PhiNode); - + Block currentBlock = startCurrentBlock; if (usage instanceof PhiNode) { // An input to a PhiNode is used at the end of the predecessor block that corresponds to // the PhiNode input. @@ -763,7 +772,10 @@ Block mergeBlock = cfg.getNodeToBlock().get(merge); for (int i = 0; i < phi.valueCount(); ++i) { if (phi.valueAt(i) == node) { - closure.apply(mergeBlock.getPredecessors().get(i)); + currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, mergeBlock.getPredecessors().get(i)); + if (currentBlock == earliestBlock) { + break; + } } } } else if (usage instanceof VirtualState) { @@ -773,19 +785,19 @@ if (unscheduledUsage instanceof VirtualState) { // If a FrameState is an outer FrameState this method behaves as if the inner // FrameState was the actual usage, by recursing. - blocksForUsage(node, unscheduledUsage, closure, strategy); + currentBlock = blocksForUsage(node, unscheduledUsage, currentBlock, earliestBlock, strategy); } else if (unscheduledUsage instanceof AbstractBeginNode) { // Only FrameStates can be connected to BeginNodes. if (!(usage instanceof FrameState)) { throw new SchedulingError(usage.toString()); } if (unscheduledUsage instanceof StartNode) { - closure.apply(cfg.getNodeToBlock().get(unscheduledUsage)); + currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(unscheduledUsage)); } else { // If a FrameState belongs to a BeginNode then it's inputs will be placed at // the common dominator of all EndNodes. for (Node pred : unscheduledUsage.cfgPredecessors()) { - closure.apply(cfg.getNodeToBlock().get(pred)); + currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(pred)); } } } else { @@ -798,21 +810,18 @@ } // Otherwise: Put the input into the same block as the usage. assignBlockToNode((ValueNode) unscheduledUsage, strategy); - closure.apply(cfg.getNodeToBlock().get(unscheduledUsage)); + currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(unscheduledUsage)); + } + if (currentBlock == earliestBlock) { + break; } } } else { // All other types of usages: Put the input into the same block as the usage. assignBlockToNode((ValueNode) usage, strategy); - closure.apply(cfg.getNodeToBlock().get(usage)); + currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(usage)); } - } - - private void ensureScheduledUsages(Node node, SchedulingStrategy strategy) { - for (Node usage : node.usages().filter(ValueNode.class)) { - assignBlockToNode((ValueNode) usage, strategy); - } - // now true usages are ready + return currentBlock; } private void sortNodesWithinBlocks(StructuredGraph graph, SchedulingStrategy strategy) { @@ -1071,20 +1080,16 @@ return; } + addToLatestSortingHelper(i, state); + } + + private void addToLatestSortingHelper(ValueNode i, SortState state) { FrameState stateAfter = null; if (i instanceof StateSplit) { stateAfter = ((StateSplit) i).stateAfter(); } - for (Node input : i.inputs()) { - if (input instanceof FrameState) { - if (input != stateAfter) { - addUnscheduledToLatestSorting((FrameState) input, state); - } - } else { - addToLatestSorting((ValueNode) input, state); - } - } + addInputsToLatestSorting(i, state, stateAfter); if (state.readsSize() != 0) { if (i instanceof MemoryCheckpoint.Single) { @@ -1112,6 +1117,18 @@ } } + private void addInputsToLatestSorting(ValueNode i, SortState state, FrameState stateAfter) { + for (Node input : i.inputs()) { + if (input instanceof FrameState) { + if (input != stateAfter) { + addUnscheduledToLatestSorting((FrameState) input, state); + } + } else { + addToLatestSorting((ValueNode) input, state); + } + } + } + /** * Sorts the nodes within a block by adding the nodes to a list in a post-order iteration over * all usages. The resulting list is reversed to create an earliest-possible scheduling of
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Mon Feb 23 20:13:29 2015 +0100 @@ -33,7 +33,6 @@ import com.oracle.graal.compiler.gen.*; import com.oracle.graal.graph.*; import com.oracle.graal.java.*; -import com.oracle.graal.java.BciBlockMapping.BciBlock; import com.oracle.graal.lir.*; import com.oracle.graal.lir.alloc.lsra.*; import com.oracle.graal.lir.alloc.lsra.Interval.*; @@ -131,10 +130,10 @@ * @param label A label describing the compilation phase that produced the control flow graph. * @param blocks The list of blocks to be printed. */ - public void printCFG(String label, List<? extends AbstractBlock<?>> blocks, boolean printNodes) { + public void printCFG(String label, List<? extends AbstractBlockBase<?>> blocks, boolean printNodes) { if (lir == null) { latestScheduling = new NodeMap<>(cfg.getNodeToBlock()); - for (AbstractBlock<?> abstractBlock : blocks) { + for (AbstractBlockBase<?> abstractBlock : blocks) { Block block = (Block) abstractBlock; Node cur = block.getBeginNode(); while (true) { @@ -152,7 +151,7 @@ begin("cfg"); out.print("name \"").print(label).println('"'); - for (AbstractBlock<?> block : blocks) { + for (AbstractBlockBase<?> block : blocks) { printBlock(block, printNodes); } end("cfg"); @@ -194,7 +193,7 @@ } } - private void printBlock(AbstractBlock<?> block, boolean printNodes) { + private void printBlock(AbstractBlockBase<?> block, boolean printNodes) { printBlockProlog(block); if (printNodes) { assert block instanceof Block; @@ -203,31 +202,24 @@ printBlockEpilog(block); } - private void printBlockEpilog(AbstractBlock<?> block) { + private void printBlockEpilog(AbstractBlockBase<?> block) { printLIR(block); end("block"); } - private void printBlockProlog(AbstractBlock<?> block) { + private void printBlockProlog(AbstractBlockBase<?> block) { begin("block"); out.print("name \"").print(blockToString(block)).println('"'); - if (block instanceof BciBlock) { - out.print("from_bci ").println(((BciBlock) block).startBci); - out.print("to_bci ").println(((BciBlock) block).endBci); - } else { - out.println("from_bci -1"); - out.println("to_bci -1"); - } out.print("predecessors "); - for (AbstractBlock<?> pred : block.getPredecessors()) { + for (AbstractBlockBase<?> pred : block.getPredecessors()) { out.print("\"").print(blockToString(pred)).print("\" "); } out.println(); out.print("successors "); - for (AbstractBlock<?> succ : block.getSuccessors()) { + for (AbstractBlockBase<?> succ : block.getSuccessors()) { if (!succ.isExceptionEntry()) { out.print("\"").print(blockToString(succ)).print("\" "); } @@ -235,7 +227,7 @@ out.println(); out.print("xhandlers"); - for (AbstractBlock<?> succ : block.getSuccessors()) { + for (AbstractBlockBase<?> succ : block.getSuccessors()) { if (succ.isExceptionEntry()) { out.print("\"").print(blockToString(succ)).print("\" "); } @@ -437,7 +429,7 @@ * * @param block the block to print */ - private void printLIR(AbstractBlock<?> block) { + private void printLIR(AbstractBlockBase<?> block) { if (lir == null) { return; } @@ -500,7 +492,7 @@ return prefix + node.toString(Verbosity.Id); } - private String blockToString(AbstractBlock<?> block) { + private String blockToString(AbstractBlockBase<?> block) { if (lir == null && schedule == null && block instanceof Block) { // During all the front-end phases, the block schedule is built only for the debug // output.
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java Mon Feb 23 20:13:29 2015 +0100 @@ -723,7 +723,7 @@ assert checkAllVarargPlaceholdersAreDeleted(parameterCount, placeholders); - new FloatingReadPhase(false, true, false).apply(snippetCopy); + new FloatingReadPhase(false, true).apply(snippetCopy); MemoryAnchorNode memoryAnchor = snippetCopy.add(new MemoryAnchorNode()); snippetCopy.start().replaceAtUsages(InputType.Memory, memoryAnchor); @@ -748,7 +748,7 @@ List<MemoryMapNode> memMaps = returnNodes.stream().map(n -> n.getMemoryMap()).collect(Collectors.toList()); ValueNode returnValue = InliningUtil.mergeReturns(merge, returnNodes, null); this.returnNode = snippet.add(new ReturnNode(returnValue)); - MemoryMapImpl mmap = FloatingReadPhase.mergeMemoryMaps(merge, memMaps, false); + MemoryMapImpl mmap = FloatingReadPhase.mergeMemoryMaps(merge, memMaps); MemoryMapNode memoryMap = snippet.unique(new MemoryMapNode(mmap.getMap())); this.returnNode.setMemoryMap(memoryMap); for (MemoryMapNode mm : memMaps) {
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectsPhase.java Thu Feb 12 15:41:44 2015 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectsPhase.java Mon Feb 23 20:13:29 2015 +0100 @@ -101,7 +101,7 @@ Debug.dump(graph, "after " + getName() + " iteration"); } - new DeadCodeEliminationPhase(Optional).apply(graph); + new DeadCodeEliminationPhase(Required).apply(graph); Set<Node> changedNodes = listener.getNodes(); for (Node node : graph.getNodes()) {