Mercurial > hg > truffle
changeset 4330:d13bfce7b3dd
Merge
| author | Gilles Duboscq <duboscq@ssw.jku.at> |
|---|---|
| date | Thu, 26 Jan 2012 12:23:00 +0100 |
| parents | 4aacce9c9cb9 (diff) b0aa4a52b89c (current diff) |
| children | daaee28c65c6 |
| files | graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/LIRVerifier.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBranch.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRCall.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIROpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/MoveInstruction.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/StandardOpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/package-info.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64ArithmeticOpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64CallOpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64CompareOpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64ControlFlowOpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64ConvertOpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64DivOpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LogicFloatOpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64MoveOpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64MulOpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64Op1Opcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64ShiftOpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64StandardOpcode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64XirOpcode.java graal/com.oracle.max.graal.snippets/src/com/oracle/max/graal/snippets/target/amd64/AMD64MathIntrinsicOpcode.java mx/commands.py |
| diffstat | 23 files changed, 125 insertions(+), 1418 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompiler.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompiler.java Thu Jan 26 12:23:00 2012 +0100 @@ -187,11 +187,6 @@ plan.runPhases(PhasePosition.HIGH_LEVEL, graph, context); if (GraalOptions.OptLoops) { - graph.mark(); - new FindInductionVariablesPhase().apply(graph, context); - if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase(target, runtime, true, assumptions).apply(graph, context); - } new SafepointPollingEliminationPhase().apply(graph, context); } @@ -209,14 +204,6 @@ new LoweringPhase(runtime).apply(graph, context); new CanonicalizerPhase(target, runtime, true, assumptions).apply(graph, context); - if (GraalOptions.OptLoops) { - graph.mark(); - new RemoveInductionVariablesPhase().apply(graph, context); - if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase(target, runtime, true, assumptions).apply(graph, context); - } - } - if (GraalOptions.Lower) { new FloatingReadPhase().apply(graph, context);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/loop/Loop.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/loop/Loop.java Thu Jan 26 12:23:00 2012 +0100 @@ -75,12 +75,12 @@ return parent == l || (parent != null && parent.isChildOf(l)); } - public boolean localContainsFixed(FixedNode n) { + public boolean containsDirectFixed(FixedNode n) { return directCFGNodes.isMarked(n); } public boolean containsFixed(FixedNode n) { - if (localContainsFixed(n)) { + if (containsDirectFixed(n)) { return true; } for (Loop child : children()) { @@ -104,7 +104,7 @@ } @SuppressWarnings("unchecked") - public Iterable<FixedNode> fixedNodes() { + public Iterable<FixedNode> directFixedNodes() { return (Iterable) directCFGNodes; } @@ -113,7 +113,7 @@ loop.parent = this; } - NodeBitMap directCFGNode() { + NodeBitMap directCFGNodes() { return directCFGNodes; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/loop/LoopInfo.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/loop/LoopInfo.java Thu Jan 26 12:23:00 2012 +0100 @@ -65,17 +65,26 @@ } } - private void print(Loop loop) { - TTY.println("%s", loop.loopBegin()); - TTY.println("-- subnodes"); - for (Node node : loop.fixedNodes()) { - TTY.println(" " + node); + private void print(final Loop loop) { + TTY.out().printf("%s\n", loop.loopBegin()); + TTY.out().println("-- exits"); + TTY.out().adjustIndentation(+2); + for (Node n : loop.exits()) { + TTY.out().printf("%s from %s\n", n, n.predecessor()); } - TTY.println("-- subloops"); + TTY.out().adjustIndentation(-2); + TTY.out().println("-- directNodes"); + TTY.out().adjustIndentation(+2); + for (final Node node : loop.directFixedNodes()) { + TTY.out().printf("%s\n", node); + } + TTY.out().adjustIndentation(-2); + TTY.out().println("-- subloops"); + TTY.out().adjustIndentation(+2); for (Loop sub : loop.children()) { print(sub); } - TTY.println("-- sub"); - TTY.println(); + TTY.out().adjustIndentation(-2); + TTY.out().println("-- sub"); } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/loop/LoopUtil.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/loop/LoopUtil.java Thu Jan 26 12:23:00 2012 +0100 @@ -53,11 +53,13 @@ //Find exits for (Loop loop : info.loops()) { - for (FixedNode n : loop.fixedNodes()) { + for (FixedNode n : loop.directFixedNodes()) { if (n instanceof ControlSplitNode) { for (BeginNode sux : ((ControlSplitNode) n).blockSuccessors()) { - if (!loop.containsFixed(sux)) { - loop.exits().mark(sux); + Loop l = loop; + while (l != null && !l.containsFixed(sux)) { + l.exits().mark(sux); + l = l.parent(); } } } @@ -103,10 +105,10 @@ mark((LoopBeginNode) n, nodeToLoop); } else { if (oldMark != null) { - oldMark.directCFGNode().clear(n); + oldMark.directCFGNodes().clear(n); } nodeToLoop.set(n, loop); - loop.directCFGNode().mark(n); + loop.directCFGNodes().mark(n); } } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/FindInductionVariablesPhase.java Thu Jan 26 10:54:23 2012 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,162 +0,0 @@ -/* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.max.graal.compiler.phases; - -import java.util.*; - -import com.oracle.max.cri.ci.*; -import com.oracle.max.graal.compiler.util.*; -import com.oracle.max.graal.compiler.util.LoopUtil.Loop; -import com.oracle.max.graal.graph.*; -import com.oracle.max.graal.nodes.*; -import com.oracle.max.graal.nodes.calc.*; -import com.oracle.max.graal.nodes.loop.*; - - -/** - * Looks for linear induction variables in loops. - * Saves the information in the graph by replacing these induction variables computations with subclasses of {@link InductionVariableNode} : - * <ul> - * <li> {@link LoopCounterNode} is the iteration counter (from 0 to Niter)</li> - * <li> {@link BasicInductionVariableNode} is an induction variable of the form {@code stride * loopCount + init}. Computed using a phi and an add node</li> - * <li> {@link DerivedInductionVariableNode} is an induction variable of the form {@code scale * base + offset} where base is an other of {@link InductionVariableNode}. Computed using multiply and add</li> - * </ul> - * This phase works in collaboration with {@link RemoveInductionVariablesPhase} which will convert the {@link InductionVariableNode}s back to phis and arithmetic nodes. - */ -public class FindInductionVariablesPhase extends Phase { - - @Override - protected void run(StructuredGraph graph) { - List<Loop> loops = LoopUtil.computeLoops(graph); - - for (Loop loop : loops) { - findInductionVariables(loop); - } - } - - private static void findInductionVariables(Loop loop) { - LoopBeginNode loopBegin = loop.loopBegin(); - NodeBitMap loopNodes = loop.nodes(); - for (PhiNode phi : loopBegin.phis().snapshot()) { - ValueNode init = phi.valueAt(loopBegin.forwardEdge()); - ValueNode backEdge = phi.valueAt(loopBegin.loopEnd()); - if (loopNodes.isNew(init) || loopNodes.isNew(backEdge)) { - continue; - } - if (loopNodes.isMarked(backEdge)) { - if (backEdge instanceof IntegerAddNode || backEdge instanceof IntegerSubNode) { - final IntegerArithmeticNode arithmetic = (IntegerArithmeticNode) backEdge; - ValueNode stride; - if (arithmetic.x() == phi) { - stride = arithmetic.y(); - } else if (arithmetic.y() == phi) { - stride = arithmetic.x(); - } else { - continue; - } - if (loopNodes.isNotNewNotMarked(stride)) { - Graph graph = loopBegin.graph(); - if (arithmetic instanceof IntegerSubNode) { - stride = graph.unique(new NegateNode(stride)); - } - CiKind kind = phi.kind(); - LoopCounterNode counter = loopBegin.loopCounter(kind); - BasicInductionVariableNode biv1 = null; - BasicInductionVariableNode biv2 = null; - if (phi.usages().size() > 1) { - biv1 = graph.add(new BasicInductionVariableNode(kind, init, stride, counter)); - ((StructuredGraph) phi.graph()).replaceFloating(phi, biv1); - } else { - phi.replaceFirstInput(arithmetic, null); - phi.safeDelete(); - } - if (arithmetic.usages().size() > 0) { - biv2 = graph.add(new BasicInductionVariableNode(kind, IntegerArithmeticNode.add(init, stride), stride, counter)); - ((StructuredGraph) arithmetic.graph()).replaceFloating(arithmetic, biv2); - } else { - arithmetic.safeDelete(); - } - if (biv1 != null) { - findDerivedInductionVariable(biv1, kind, loopNodes); - } - if (biv2 != null) { - findDerivedInductionVariable(biv2, kind, loopNodes); - } - } - } - } - } - } - private static void findDerivedInductionVariable(BasicInductionVariableNode biv, CiKind kind, NodeBitMap loopNodes) { - for (Node usage : biv.usages().snapshot()) { - ValueNode scale = scale(usage, biv, loopNodes); - ValueNode offset = null; - Node node = null; - if (scale == null) { - if (usage instanceof IntegerAddNode) { - IntegerAddNode add = (IntegerAddNode) usage; - if (add.x() == biv || (scale = scale(add.x(), biv, loopNodes)) != null) { - offset = add.y(); - } else if (add.y() == biv || (scale = scale(add.y(), biv, loopNodes)) != null) { - offset = add.x(); - } - if (offset != null) { - if (loopNodes.isNotNewNotMarked(offset)) { - node = add; - } else { - offset = null; - } - } - } - } else { - node = usage; - } - if (scale != null || offset != null) { - if (scale == null) { - scale = ConstantNode.forIntegerKind(kind, 1, biv.graph()); - } else if (offset == null) { - offset = ConstantNode.forIntegerKind(kind, 0, biv.graph()); - } - DerivedInductionVariableNode div = biv.graph().add(new DerivedInductionVariableNode(kind, offset, scale, biv)); - assert node instanceof FloatingNode; - ((StructuredGraph) node.graph()).replaceFloating((FloatingNode) node, div); - } - } - } - - private static ValueNode scale(Node n, BasicInductionVariableNode biv, NodeBitMap loopNodes) { - if (n instanceof IntegerMulNode) { - IntegerMulNode mul = (IntegerMulNode) n; - ValueNode scale = null; - if (mul.x() == biv) { - scale = mul.y(); - } else if (mul.y() == biv) { - scale = mul.x(); - } - if (scale != null && loopNodes.isNotNewNotMarked(scale)) { - return scale; - } - } - return null; - } -}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/RemoveInductionVariablesPhase.java Thu Jan 26 10:54:23 2012 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,94 +0,0 @@ -/* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.max.graal.compiler.phases; - -import java.util.*; -import java.util.Map.Entry; - -import com.oracle.max.graal.graph.*; -import com.oracle.max.graal.nodes.*; -import com.oracle.max.graal.nodes.loop.*; - -/** - * This phase looks for {@link InductionVariableNode}s and converts them to Phis and arithmetic nodes. - */ -public class RemoveInductionVariablesPhase extends Phase { - - private NodeMap<ValueNode> loweredIV; - - @Override - protected void run(StructuredGraph graph) { - loweredIV = graph.createNodeMap(); - - for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.class)) { - Collection<InductionVariableNode> inductionVariables = loopBegin.inductionVariables(); - Map<InductionVariableNode, InductionVariableNode> nextIterOf = null; - for (InductionVariableNode iv1 : inductionVariables) { - for (InductionVariableNode iv2 : inductionVariables) { - if (iv1 != iv2 && iv1.isNextIteration(iv2)) { - if (nextIterOf == null) { - nextIterOf = new IdentityHashMap<>(); - } - nextIterOf.put(iv2, iv1); - } - } - } - - for (InductionVariableNode iv : inductionVariables) { - if (nextIterOf == null || !nextIterOf.containsKey(iv)) { - loweredIV.set(iv, iv.lowerInductionVariable()); - } - } - - if (nextIterOf != null) { - for (Entry<InductionVariableNode, InductionVariableNode> entry : nextIterOf.entrySet()) { - InductionVariableNode it = entry.getValue(); - InductionVariableNode nextIt = entry.getKey(); - // can't fuse if nextIt is used in the loopBegin's framestate because this would pop the backedge value out of the loop in scheduler - if (it != null && !nextIt.usages().contains(loopBegin.stateAfter())) { - ValueNode itValue = loweredIV.get(it); - if (itValue instanceof PhiNode) { - PhiNode phi = (PhiNode) itValue; - loweredIV.set(nextIt, phi.valueAt(loopBegin.loopEnd())); - continue; - } - } - loweredIV.set(nextIt, nextIt.lowerInductionVariable()); - } - } - } - for (Entry<Node, ValueNode> entry : loweredIV.entries()) { - InductionVariableNode iv = (InductionVariableNode) entry.getKey(); - ValueNode lower = entry.getValue(); - for (Node usage : iv.usages().snapshot()) { - if (!(usage instanceof InductionVariableNode)) { - usage.replaceFirstInput(iv, lower); - } else { - usage.replaceFirstInput(iv, null); - } - } - iv.safeDelete(); - } - } - -}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Thu Jan 26 12:23:00 2012 +0100 @@ -33,7 +33,6 @@ import com.oracle.max.graal.graph.Node.Verbosity; import com.oracle.max.graal.nodes.*; import com.oracle.max.graal.nodes.extended.*; -import com.oracle.max.graal.nodes.loop.*; import com.oracle.max.graal.nodes.virtual.*; @@ -185,11 +184,6 @@ nodeToBlock.set(usage, b); } } - if (n instanceof LoopBeginNode) { - for (InductionVariableNode iv : ((LoopBeginNode) n).inductionVariables()) { - nodeToBlock.set(iv, b); - } - } } if (n instanceof EndNode) { assert b.end() == null || n == b.end(); @@ -454,12 +448,6 @@ block = getCommonDominator(block, nodeToBlock.get(pred)); } closure.apply(block); - } else if (usage instanceof LinearInductionVariableNode) { - LinearInductionVariableNode liv = (LinearInductionVariableNode) usage; - if (liv.isLinearInductionVariableInput(node)) { - Block mergeBlock = nodeToBlock.get(liv.loopBegin()); - closure.apply(mergeBlock.dominator()); - } } else { assignBlockToNode(usage); closure.apply(nodeToBlock.get(usage)); @@ -531,7 +519,7 @@ } private void addToSorting(Block b, Node i, List<Node> sortedInstructions, NodeBitMap map) { - if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b || i instanceof PhiNode || i instanceof LocalNode || i instanceof InductionVariableNode) { + if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b || i instanceof PhiNode || i instanceof LocalNode) { return; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Thu Jan 26 10:54:23 2012 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,304 +0,0 @@ -/* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.max.graal.compiler.util; - -import java.util.*; - -import com.oracle.max.graal.compiler.schedule.*; -import com.oracle.max.graal.graph.*; -import com.oracle.max.graal.graph.Node.Verbosity; -import com.oracle.max.graal.nodes.*; -import com.oracle.max.graal.nodes.PhiNode.PhiType; - -public class LoopUtil { - - public static class Loop { - private final LoopBeginNode loopBegin; - private NodeBitMap cfgNodes; - private Loop parent; - private NodeBitMap exits; - private NodeBitMap inOrBefore; - private NodeBitMap inOrAfter; - private NodeBitMap nodes; - public Loop(LoopBeginNode loopBegin, NodeBitMap nodes, NodeBitMap exits) { - this.loopBegin = loopBegin; - this.cfgNodes = nodes; - this.exits = exits; - } - - public LoopBeginNode loopBegin() { - return loopBegin; - } - - public NodeBitMap cfgNodes() { - return cfgNodes; - } - - public NodeBitMap nodes() { - if (nodes == null) { - nodes = loopBegin().graph().createNodeBitMap(); - nodes.setUnion(inOrAfter()); - nodes.setIntersect(inOrBefore()); - } - return nodes; - } - - public Loop parent() { - return parent; - } - - public NodeBitMap exits() { - return exits; - } - - public void setParent(Loop parent) { - this.parent = parent; - } - - public boolean isChild(Loop loop) { - return loop.parent != null && (loop.parent == this || loop.parent.isChild(this)); - } - - public NodeBitMap inOrAfter() { - if (inOrAfter == null) { - inOrAfter = LoopUtil.inOrAfter(this); - } - return inOrAfter; - } - - public NodeBitMap inOrBefore() { - if (inOrBefore == null) { - inOrBefore = LoopUtil.inOrBefore(this, inOrAfter()); - } - return inOrBefore; - } - - public void invalidateCached() { - inOrAfter = null; - inOrBefore = null; - nodes = null; - } - - @Override - public String toString() { - return "Loop #" + loopBegin().toString(Verbosity.Id); - } - } - - public static List<Loop> computeLoops(StructuredGraph graph) { - List<Loop> loops = new LinkedList<>(); - for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.class)) { - NodeBitMap cfgNodes = markUpCFG(loopBegin, loopBegin.loopEnd()); // computeLoopNodes(loopBegin); - cfgNodes.mark(loopBegin); - NodeBitMap exits = computeLoopExits(loopBegin, cfgNodes); - loops.add(new Loop(loopBegin, cfgNodes, exits)); - } - for (Loop loop : loops) { - for (Loop other : loops) { - if (other != loop && other.cfgNodes().isMarked(loop.loopBegin())) { - if (loop.parent() == null || loop.parent().cfgNodes().isMarked(other.loopBegin())) { - loop.setParent(other); - } - } - } - } - return loops; - } - - public static NodeBitMap computeLoopExits(LoopBeginNode loopBegin, NodeBitMap cfgNodes) { - Graph graph = loopBegin.graph(); - NodeBitMap exits = graph.createNodeBitMap(); - for (Node n : cfgNodes) { - if (IdentifyBlocksPhase.trueSuccessorCount(n) > 1) { - for (Node sux : n.cfgSuccessors()) { - if (sux != null && !cfgNodes.isMarked(sux) && sux instanceof FixedNode) { - exits.mark(sux); - } - } - } - } - return exits; - } - - public static NodeBitMap markUpCFG(LoopBeginNode loopBegin) { - return markUpCFG(loopBegin, loopBegin.loopEnd()); - } - - public static NodeBitMap markUpCFG(LoopBeginNode loopBegin, FixedNode from) { - NodeFlood workCFG = loopBegin.graph().createNodeFlood(); - workCFG.add(from); - NodeBitMap loopNodes = loopBegin.graph().createNodeBitMap(); - for (Node n : workCFG) { - if (n == loopBegin) { - continue; - } - loopNodes.mark(n); - if (n instanceof LoopBeginNode) { - workCFG.add(((LoopBeginNode) n).loopEnd()); - } - for (Node pred : n.cfgPredecessors()) { - workCFG.add(pred); - } - } - return loopNodes; - } - - private static NodeBitMap inOrAfter(Loop loop) { - return inOrAfter(loop, loop.cfgNodes()); - } - - private static NodeBitMap inOrAfter(Loop loop, NodeBitMap cfgNodes) { - return inOrAfter(loop, cfgNodes, true); - } - - private static NodeBitMap inOrAfter(Loop loop, NodeBitMap cfgNodes, boolean full) { - Graph graph = loop.loopBegin().graph(); - NodeBitMap inOrAfter = graph.createNodeBitMap(); - NodeFlood work = graph.createNodeFlood(); - work.addAll(cfgNodes); - for (Node n : work) { - markWithState(n, inOrAfter); - if (full) { - for (Node sux : n.successors()) { - if (sux != null) { - work.add(sux); - } - } - } - for (Node usage : n.usages()) { - if (usage instanceof PhiNode) { // filter out data graph cycles - PhiNode phi = (PhiNode) usage; - MergeNode merge = phi.merge(); - if (merge instanceof LoopBeginNode) { - LoopBeginNode phiLoop = (LoopBeginNode) merge; - if (phi.valueAt(phiLoop.loopEnd()) == n) { - continue; - } - } - } - work.add(usage); - } - } - return inOrAfter; - } - - private static NodeBitMap inOrBefore(Loop loop, NodeBitMap inOrAfter) { - return inOrBefore(loop, inOrAfter, loop.cfgNodes()); - } - - private static NodeBitMap inOrBefore(Loop loop, NodeBitMap inOrAfter, NodeBitMap cfgNodes) { - return inOrBefore(loop, inOrAfter, cfgNodes, true); - } - - private static NodeBitMap inOrBefore(Loop loop, NodeBitMap inOrAfter, NodeBitMap cfgNodes, boolean full) { - Graph graph = loop.loopBegin().graph(); - NodeBitMap inOrBefore = graph.createNodeBitMap(); - NodeFlood work = graph.createNodeFlood(); - work.addAll(cfgNodes); - for (Node n : work) { - inOrBefore.mark(n); - if (full) { - if (n.predecessor() != null) { - work.add(n.predecessor()); - } - } - if (n instanceof PhiNode) { // filter out data graph cycles - PhiNode phi = (PhiNode) n; - if (phi.type() == PhiType.Value) { - int backIndex = -1; - MergeNode merge = phi.merge(); - if (merge instanceof LoopBeginNode && cfgNodes.isNotNewNotMarked(((LoopBeginNode) merge).loopEnd())) { - LoopBeginNode phiLoop = (LoopBeginNode) merge; - backIndex = phiLoop.phiPredecessorIndex(phiLoop.loopEnd()); - } - for (int i = 0; i < phi.valueCount(); i++) { - if (i != backIndex) { - work.add(phi.valueAt(i)); - } - } - } - } else { - for (Node in : n.inputs()) { - if (in != null) { - work.add(in); - } - } - if (full) { - for (Node sux : n.cfgSuccessors()) { // go down into branches that are not 'inOfAfter' - if (sux != null && !inOrAfter.isMarked(sux)) { - work.add(sux); - } - } - if (n instanceof LoopBeginNode && n != loop.loopBegin()) { - Loop p = loop.parent; - boolean isParent = false; - while (p != null) { - if (p.loopBegin() == n) { - isParent = true; - break; - } - p = p.parent; - } - if (!isParent) { - work.add(((LoopBeginNode) n).loopEnd()); - } - } - } - if (cfgNodes.isNotNewMarked(n)) { //add all values from the exits framestates - for (Node sux : n.cfgSuccessors()) { - if (loop.exits().isNotNewMarked(sux) && sux instanceof StateSplit) { - FrameState stateAfter = ((StateSplit) sux).stateAfter(); - while (stateAfter != null) { - for (Node in : stateAfter.inputs()) { - if (!(in instanceof FrameState)) { - work.add(in); - } - } - stateAfter = stateAfter.outerFrameState(); - } - } - } - } - if (n instanceof MergeNode) { //add phis & counters - for (Node usage : n.usages()) { - if (!(usage instanceof LoopEndNode)) { - work.add(usage); - } - } - } - } - } - return inOrBefore; - } - - private static void markWithState(Node n, NodeBitMap map) { - map.mark(n); - if (n instanceof StateSplit) { - FrameState stateAfter = ((StateSplit) n).stateAfter(); - while (stateAfter != null) { - map.mark(stateAfter); - stateAfter = stateAfter.outerFrameState(); - } - } - } -}
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java Thu Jan 26 12:23:00 2012 +0100 @@ -160,4 +160,8 @@ public Iterator<Node> iterator() { return new MarkedNodeIterator(NodeBitMap.this, graph().getNodes().iterator()); } + + public int cardinality() { + return bitMap.cardinality(); + } }
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeUsagesList.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeUsagesList.java Thu Jan 26 12:23:00 2012 +0100 @@ -48,10 +48,16 @@ return size; } + @Override public boolean isEmpty() { return size == 0; } + @Override + public boolean isNotEmpty() { + return size > 0; + } + protected void incModCount() { modCount++; }
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/iterators/FilteredNodeIterable.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/iterators/FilteredNodeIterable.java Thu Jan 26 12:23:00 2012 +0100 @@ -43,6 +43,14 @@ this.predicate = predicate.or(new TypePredicate(clazz)); return (FilteredNodeIterable<Node>) this; } + public FilteredNodeIterable<T> and(NodePredicate nodePredicate) { + this.predicate = this.predicate.and(nodePredicate); + return this; + } + public FilteredNodeIterable<T> or(NodePredicate nodePredicate) { + this.predicate = this.predicate.or(nodePredicate); + return this; + } @Override public Iterator<T> iterator() { final Iterator<T> iterator = nodeIterable.iterator();
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/iterators/NodeIterable.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/iterators/NodeIterable.java Thu Jan 26 12:23:00 2012 +0100 @@ -39,6 +39,9 @@ public <F extends T> FilteredNodeIterable<F> filter(Class<F> clazz) { return new FilteredNodeIterable<>(this).and(clazz); } + public FilteredNodeIterable<T> filter(NodePredicate predicate) { + return new FilteredNodeIterable<>(this).and(predicate); + } public List<T> snapshot() { ArrayList<T> list = new ArrayList<>(); for (T n : this) { @@ -53,4 +56,19 @@ } return null; } + public int count() { + int count = 0; + Iterator<T> iterator = iterator(); + while (iterator.hasNext()) { + iterator.next(); + count++; + } + return count; + } + public boolean isEmpty() { + return count() == 0; + } + public boolean isNotEmpty() { + return iterator().hasNext(); + } }
--- a/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/GraphBuilderPhase.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/GraphBuilderPhase.java Thu Jan 26 12:23:00 2012 +0100 @@ -712,11 +712,16 @@ private void genInstanceOf() { int cpi = stream().readCPI(); RiType type = lookupType(cpi, INSTANCEOF); - ConstantNode typeInstruction = genTypeOrDeopt(RiType.Representation.ObjectHub, type, type instanceof RiResolvedType); ValueNode object = frameState.apop(); - if (typeInstruction != null) { - frameState.ipush(append(MaterializeNode.create(currentGraph.unique(new InstanceOfNode(typeInstruction, (RiResolvedType) type, object, false)), currentGraph))); + if (type instanceof RiResolvedType) { + ConstantNode hub = appendConstant(((RiResolvedType) type).getEncoding(RiType.Representation.ObjectHub)); + frameState.ipush(append(MaterializeNode.create(currentGraph.unique(new InstanceOfNode(hub, (RiResolvedType) type, object, false)), currentGraph))); } else { + PlaceholderNode trueSucc = currentGraph.add(new PlaceholderNode()); + DeoptimizeNode deopt = currentGraph.add(new DeoptimizeNode(DeoptAction.InvalidateRecompile)); + IfNode ifNode = currentGraph.add(new IfNode(currentGraph.unique(new NullCheckNode(object, true)), trueSucc, deopt, 1)); + append(ifNode); + lastInstr = trueSucc; frameState.ipush(appendConstant(CiConstant.INT_0)); } }
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/LoopBeginNode.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/LoopBeginNode.java Thu Jan 26 12:23:00 2012 +0100 @@ -24,9 +24,7 @@ import java.util.*; -import com.oracle.max.cri.ci.*; import com.oracle.max.graal.graph.*; -import com.oracle.max.graal.nodes.loop.*; import com.oracle.max.graal.nodes.spi.*; @@ -85,20 +83,6 @@ throw ValueUtil.shouldNotReachHere(); } - public Collection<InductionVariableNode> inductionVariables() { - // TODO (gd) produces useless garbage - List<InductionVariableNode> list = new LinkedList<>(); - collectInductionVariables(this, list); - return list; - } - - private static void collectInductionVariables(Node node, Collection<InductionVariableNode> collection) { - for (InductionVariableNode iv : node.usages().filter(InductionVariableNode.class)) { - collection.add(iv); - collectInductionVariables(iv, collection); - } - } - @Override public Iterable<? extends Node> phiPredecessors() { return Arrays.asList(new Node[]{this.forwardEdge(), this.loopEnd()}); @@ -108,19 +92,6 @@ return this.endAt(0); } - public LoopCounterNode loopCounter() { - return loopCounter(CiKind.Long); - } - - public LoopCounterNode loopCounter(CiKind kind) { - for (LoopCounterNode counter : usages().filter(LoopCounterNode.class)) { - if (counter.kind() == kind) { - return counter; - } - } - return graph().add(new LoopCounterNode(kind, this)); - } - @Override public boolean verify() { assertTrue(loopEnd() != null, "missing loopEnd");
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/loop/BasicInductionVariableNode.java Thu Jan 26 10:54:23 2012 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,160 +0,0 @@ -/* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.max.graal.nodes.loop; - -import com.oracle.max.cri.ci.*; -import com.oracle.max.graal.nodes.*; -import com.oracle.max.graal.nodes.PhiNode.PhiType; -import com.oracle.max.graal.nodes.calc.*; -import com.oracle.max.graal.nodes.spi.*; - -/** - * LinearInductionVariable that is computed in the loops thanks to Phi(init, this + stride). - * This will keep at least one register busy in the whole loop body - */ -public class BasicInductionVariableNode extends LinearInductionVariableNode implements Canonicalizable { - - @Input private LoopCounterNode loopCounter; - - public BasicInductionVariableNode(CiKind kind, ValueNode init, ValueNode stride, LoopCounterNode loopCounter) { - super(kind, stride, init); - this.loopCounter = loopCounter; - } - - public LoopCounterNode loopCounter() { - return loopCounter; - } - - public ValueNode init() { - return b(); - } - - public void setInit(ValueNode init) { - setB(init); - } - - @Override - public ValueNode stride() { - return a(); - } - - public void setStride(ValueNode stride) { - setA(stride); - } - - @Override - public LoopBeginNode loopBegin() { - return loopCounter().loopBegin(); - } - - @Override - public void peelOneIteration() { - this.setInit(IntegerArithmeticNode.add(init(), stride())); - } - - /** - * Will lessen the register pressure but augment the code complexity with a multiplication. - * @return the new DerivedInductionVariable - */ - public DerivedInductionVariableNode toDerivedInductionVariable() { - DerivedInductionVariableNode newDIV = graph().add(new DerivedInductionVariableNode(kind(), init(), stride(), loopCounter())); - ((StructuredGraph) graph()).replaceFloating(this, newDIV); - return newDIV; - } - - @Override - public ValueNode canonical(CanonicalizerTool tool) { - if (this.init().isConstant() && this.init().asConstant().asLong() == 0 && this.stride().isConstant() && this.stride().asConstant().asLong() == 1) { - return this.loopCounter(); - } - return this; - } - - @Override - public ValueNode lowerInductionVariable() { - return ivToPhi(loopBegin(), init(), stride(), kind()); - } - - @Override - public boolean isNextIteration(InductionVariableNode other) { - if (other instanceof LoopCounterNode && this.loopCounter() == other) { - if (this.init().isConstant() && this.init().asConstant().asLong() == -1 && this.stride().isConstant() && this.stride().asConstant().asLong() == 1) { - return true; - } - } else if (other instanceof LinearInductionVariableNode) { - if ((other instanceof BasicInductionVariableNode && ((BasicInductionVariableNode) other).loopCounter() == loopCounter()) - || (other instanceof DerivedInductionVariableNode && ((DerivedInductionVariableNode) other).base() == loopCounter())) { - LinearInductionVariableNode liv = (LinearInductionVariableNode) other; - if (liv.a() == stride() && IntegerAddNode.isIntegerAddition(liv.b(), init(), stride())) { - return true; - } - } - } - return false; - } - - public static PhiNode ivToPhi(LoopBeginNode loopBegin, ValueNode init, ValueNode stride, CiKind kind) { - PhiNode phi = loopBegin.graph().add(new PhiNode(kind, loopBegin, PhiType.Value)); - IntegerArithmeticNode after = IntegerArithmeticNode.add(phi, stride); - phi.addInput(init); - phi.addInput(after); - return phi; - } - - @Override - public StrideDirection strideDirection() { - ValueNode stride = stride(); - if (stride.isConstant()) { - long val = stride.asConstant().asLong(); - if (val > 0) { - return StrideDirection.Up; - } - if (val < 0) { - return StrideDirection.Down; - } - } - return null; - } - - @Override - public ValueNode minValue(FixedNode point) { - StrideDirection strideDirection = strideDirection(); - if (strideDirection == StrideDirection.Up) { - return init(); - } else if (strideDirection == StrideDirection.Down) { - return searchExtremum(point, StrideDirection.Down); - } - return null; - } - - @Override - public ValueNode maxValue(FixedNode point) { - StrideDirection strideDirection = strideDirection(); - if (strideDirection == StrideDirection.Down) { - return init(); - } else if (strideDirection == StrideDirection.Up) { - return searchExtremum(point, StrideDirection.Up); - } - return null; - } -}
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/loop/DerivedInductionVariableNode.java Thu Jan 26 10:54:23 2012 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,209 +0,0 @@ -/* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.max.graal.nodes.loop; - -import com.oracle.max.cri.ci.*; -import com.oracle.max.graal.nodes.*; -import com.oracle.max.graal.nodes.calc.*; -import com.oracle.max.graal.nodes.spi.*; - -/** - * LinearInductionVariable that is computed in the loops with offset + scale * base. - * This is computed in the loop only when necessary, puts less pressure on registers. - */ -public class DerivedInductionVariableNode extends LinearInductionVariableNode implements Canonicalizable { - - @Input private InductionVariableNode base; - - public DerivedInductionVariableNode(CiKind kind, ValueNode offset, ValueNode scale, InductionVariableNode base) { - super(kind, scale, offset); - this.base = base; - } - - public InductionVariableNode base() { - return base; - } - - public ValueNode offset() { - return b(); - } - - public void setOffset(ValueNode offset) { - setB(offset); - } - - public ValueNode scale() { - return a(); - } - - public void setScale(ValueNode scale) { - setA(scale); - } - - @Override - public LoopBeginNode loopBegin() { - return base().loopBegin(); - } - - @Override - public void peelOneIteration() { - // nop - } - - /** - * This will apply strength reduction to this induction variable but will augment register pressure in the loop. - * @return the new BasicInductionVariable - */ - public BasicInductionVariableNode toBasicInductionVariable() { - InductionVariableNode b = base(); - if (b instanceof DerivedInductionVariableNode) { - b = ((DerivedInductionVariableNode) b).toBasicInductionVariable(); - } - ValueNode init; - ValueNode stride; - LoopCounterNode counter; - if (b instanceof BasicInductionVariableNode) { - BasicInductionVariableNode basic = (BasicInductionVariableNode) b; - // let the canonicalizer do its job with this - init = IntegerArithmeticNode.add(offset(), IntegerArithmeticNode.mul(scale(), basic.init())); - stride = IntegerArithmeticNode.mul(scale(), basic.stride()); - counter = basic.loopCounter(); - } else { - assert b instanceof LoopCounterNode; - init = offset(); - stride = scale(); - counter = (LoopCounterNode) b; - } - BasicInductionVariableNode newBIV = graph().add(new BasicInductionVariableNode(kind(), init, stride, counter)); - ((StructuredGraph) graph()).replaceFloating(this, newBIV); - return newBIV; - } - - @Override - public ValueNode lowerInductionVariable() { - return IntegerArithmeticNode.add(offset(), IntegerArithmeticNode.mul(scale(), base())); - } - - @Override - public ValueNode canonical(CanonicalizerTool tool) { - if (base() instanceof DerivedInductionVariableNode) { - DerivedInductionVariableNode divBase = (DerivedInductionVariableNode) base(); - IntegerArithmeticNode newOffset = IntegerArithmeticNode.add(offset(), IntegerArithmeticNode.mul(scale(), divBase.offset())); - IntegerArithmeticNode newScale = IntegerArithmeticNode.mul(scale(), divBase.scale()); - return graph().add(new DerivedInductionVariableNode(kind(), newOffset, newScale, divBase.base())); - } - return this; - } - - @Override - public boolean isNextIteration(InductionVariableNode other) { - if (other instanceof LoopCounterNode && this.base() == other) { - if (this.offset().isConstant() && this.offset().asConstant().asLong() == -1 && this.scale().isConstant() && this.scale().asConstant().asLong() == 1) { - return true; - } - } else if (other instanceof LinearInductionVariableNode) { - if ((other instanceof BasicInductionVariableNode && ((BasicInductionVariableNode) other).loopCounter() == base()) - || (other instanceof DerivedInductionVariableNode && ((DerivedInductionVariableNode) other).base() == base())) { - LinearInductionVariableNode liv = (LinearInductionVariableNode) other; - if (liv.a() == scale() && IntegerAddNode.isIntegerAddition(liv.b(), offset(), scale())) { - return true; - } - } - } - return false; - } - - @Override - public StrideDirection strideDirection() { - switch (scaleDirection()) { - case Up: - return base().strideDirection(); - case Down: - return StrideDirection.opposite(base().strideDirection()); - } - return null; - } - - public StrideDirection scaleDirection() { - ValueNode stride = scale(); - if (stride.isConstant()) { - long val = stride.asConstant().asLong(); - if (val > 0) { - return StrideDirection.Up; - } - if (val < 0) { - return StrideDirection.Down; - } - } - return null; - } - - @Override - public ValueNode stride() { - return IntegerArithmeticNode.mul(scale(), base().stride()); - } - - @Override - public ValueNode minValue(FixedNode point) { - StrideDirection strideDirection = strideDirection(); - if (strideDirection == StrideDirection.Up) { - StrideDirection scaleDirection = scaleDirection(); - if (scaleDirection == StrideDirection.Up) { - ValueNode baseMinValue = base().minValue(point); - if (baseMinValue != null) { - return IntegerArithmeticNode.add(offset(), IntegerArithmeticNode.mul(scale(), baseMinValue)); - } - } else if (scaleDirection == StrideDirection.Down) { - ValueNode baseMaxValue = base().maxValue(point); - if (baseMaxValue != null) { - return IntegerArithmeticNode.add(offset(), IntegerArithmeticNode.mul(scale(), baseMaxValue)); - } - } - } else if (strideDirection == StrideDirection.Down) { - return searchExtremum(point, StrideDirection.Down); - } - return null; - } - - @Override - public ValueNode maxValue(FixedNode point) { - StrideDirection strideDirection = strideDirection(); - if (strideDirection == StrideDirection.Down) { - StrideDirection scaleDirection = scaleDirection(); - if (scaleDirection == StrideDirection.Up) { - ValueNode baseMaxValue = base().maxValue(point); - if (baseMaxValue != null) { - return IntegerArithmeticNode.add(offset(), IntegerArithmeticNode.mul(scale(), baseMaxValue)); - } - } else if (scaleDirection == StrideDirection.Down) { - ValueNode baseMinValue = base().minValue(point); - if (baseMinValue != null) { - return IntegerArithmeticNode.add(offset(), IntegerArithmeticNode.mul(scale(), baseMinValue)); - } - } - } else if (strideDirection == StrideDirection.Up) { - return searchExtremum(point, StrideDirection.Up); - } - return null; - } -}
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/loop/InductionVariableNode.java Thu Jan 26 10:54:23 2012 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,155 +0,0 @@ -/* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.max.graal.nodes.loop; - -import com.oracle.max.cri.ci.*; -import com.oracle.max.graal.nodes.*; -import com.oracle.max.graal.nodes.calc.*; -import com.oracle.max.graal.nodes.type.*; -import com.oracle.max.graal.util.*; - -/** - * This is a base class for all induction variables nodes. - */ -public abstract class InductionVariableNode extends FloatingNode { - - public static enum StrideDirection { - Up, - Down; - - public static StrideDirection opposite(StrideDirection d) { - if (d == Up) { - return Down; - } - if (d == Down) { - return Up; - } - return null; - } - } - - public InductionVariableNode(CiKind kind) { - super(StampFactory.forKind(kind)); - assert kind.isInt() || kind.isLong(); - } - - /** - * Retruns the loopBeginNode corresponding to the loop this induction variables is attached to. - * @return the loopBeginNode corresponding to the loop this induction variables is attached to. - */ - public abstract LoopBeginNode loopBegin(); - - /** - * This will make the induction be initialized with the value it should have had on the second iteration of the loop. - */ - public abstract void peelOneIteration(); - - /** - * Transforms this induction variable to generic nodes (Phis, arithmetics...). - * @return the generic node that computes the value of this induction variables. - */ - public abstract ValueNode lowerInductionVariable(); - - /** - * Checks if the provided induction variable is the value that this induction variable will have on the next iteration. - * @param other the induction variable this check should run against - * @return true if the provided induction variable is the value that this induction variable will have on the next iteration. - */ - public abstract boolean isNextIteration(InductionVariableNode other); - - /** - * Tries to statically find the minimum value that this induction variable can have over all possible iterations at a specific {@code point} in the CFG. - * @param point the point in the CFG from which static information will be collected - * @return the minimum value if it could be found, null otherwise - */ - public abstract ValueNode minValue(FixedNode point); - - /** - * Tries to statically find the maximum value that this induction variable can have over all possible iterations at a specific {@code point} in the CFG. - * @param point the point in the CFG from which static information will be collected - * @return the maximum value if it could be found, null otherwise - */ - public abstract ValueNode maxValue(FixedNode point); - - /** - * Tries to statically find the direction of this induction variable. - * @return returns {@link StrideDirection#Up Up} if this variable is known to be increasing, {@link StrideDirection#Down Down} if it is know to decrease, null otherwise. - */ - public abstract StrideDirection strideDirection(); - - public abstract ValueNode stride(); - - public ValueNode searchExtremum(FixedNode point, StrideDirection direction) { - LoopBeginNode upTo = loopBegin(); - //TODO (gd) collect conditions up the dominating CFG nodes path, stop as soon as we find a matching condition, it will usually be the 'narrowest' - FixedNode from = point; - - for (FixedNode node : NodeIterators.dominators(point).until(upTo)) { - if (node instanceof IfNode) { - IfNode ifNode = (IfNode) node; - if (!(ifNode.compare() instanceof CompareNode)) { - continue; - } - CompareNode compare = (CompareNode) ifNode.compare(); - ValueNode y = null; - Condition cond = null; - - if (from == ifNode.trueSuccessor()) { - cond = compare.condition(); - } else { - assert from == ifNode.falseSuccessor(); - cond = compare.condition().negate(); - } - - if (compare.x() == this) { - y = compare.y(); - } else if (compare.y() == this) { - y = compare.x(); - cond = cond.mirror(); - } - - if (y == null || !validConditionAndStrideDirection(cond, direction)) { - continue; - } - - return y; - } - from = node; - } - - return null; - } - - private static boolean validConditionAndStrideDirection(Condition cond, StrideDirection direction) { - if (direction == StrideDirection.Up) { - if (cond == Condition.LT || cond == Condition.LE) { - return true; - } - } else if (direction == StrideDirection.Down) { - if (cond == Condition.GT || cond == Condition.GE) { - return true; - } - } - return false; - } -}
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/loop/LinearInductionVariableNode.java Thu Jan 26 10:54:23 2012 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,64 +0,0 @@ -/* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.max.graal.nodes.loop; - -import com.oracle.max.cri.ci.*; -import com.oracle.max.graal.graph.*; -import com.oracle.max.graal.nodes.*; - -/** - * InductionVariable of the form a*x+b. - */ -public abstract class LinearInductionVariableNode extends InductionVariableNode { - - @Input private ValueNode a; - @Input private ValueNode b; - - public LinearInductionVariableNode(CiKind kind, ValueNode a, ValueNode b) { - super(kind); - this.a = a; - this.b = b; - } - - protected ValueNode a() { - return a; - } - - protected ValueNode b() { - return b; - } - - protected void setA(ValueNode a) { - updateUsages(this.a, a); - this.a = a; - } - - protected void setB(ValueNode b) { - updateUsages(this.b, b); - this.b = b; - } - - public boolean isLinearInductionVariableInput(Node n) { - return n == a() || n == b(); - } -}
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/loop/LoopCounterNode.java Thu Jan 26 10:54:23 2012 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,101 +0,0 @@ -/* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.max.graal.nodes.loop; - -import com.oracle.max.cri.ci.*; -import com.oracle.max.graal.graph.*; -import com.oracle.max.graal.nodes.*; - -/** - * Counts loop iterations from 0 to Niter. - * If used directly (and not just by BasicInductionVariables) computed with Phi(0, this + 1) - */ -public final class LoopCounterNode extends InductionVariableNode { - @Input private LoopBeginNode loopBegin; - - @Override - public LoopBeginNode loopBegin() { - return loopBegin; - } - - public LoopCounterNode(CiKind kind, LoopBeginNode loopBegin) { - super(kind); - this.loopBegin = loopBegin; - } - - @Override - public void peelOneIteration() { - BasicInductionVariableNode biv = null; - for (Node usage : usages()) { - if (!(usage instanceof InductionVariableNode && ((InductionVariableNode) usage).loopBegin() == this.loopBegin())) { - if (biv == null) { - biv = createBasicInductionVariable(); - biv.peelOneIteration(); - } - usage.replaceFirstInput(this, biv); - } - } - } - - @Override - public ValueNode stride() { - return ConstantNode.forIntegerKind(kind(), 1, graph()); - } - - @Override - public ValueNode lowerInductionVariable() { - return BasicInductionVariableNode.ivToPhi(loopBegin(), minValue(null), stride(), kind()); - } - - @Override - public boolean isNextIteration(InductionVariableNode other) { - if (other instanceof LinearInductionVariableNode) { - LinearInductionVariableNode liv = (LinearInductionVariableNode) other; - if ((liv instanceof BasicInductionVariableNode && ((BasicInductionVariableNode) liv).loopCounter() == this) || (liv instanceof DerivedInductionVariableNode && ((DerivedInductionVariableNode) liv).base() == this)) { - if (liv.a().isConstant() && liv.a().asConstant().asLong() == 1 && liv.b().isConstant() && liv.b().asConstant().asLong() == 1) { - return true; - } - } - } - return false; - } - - @Override - public ValueNode minValue(FixedNode point) { - return ConstantNode.forIntegerKind(kind(), 0, graph()); - } - - @Override - public ValueNode maxValue(FixedNode point) { - return searchExtremum(point, StrideDirection.Up); - } - - @Override - public StrideDirection strideDirection() { - return StrideDirection.Up; - } - - private BasicInductionVariableNode createBasicInductionVariable() { - return graph().add(new BasicInductionVariableNode(kind(), minValue(null), stride(), this)); - } -}
--- a/graal/com.oracle.max.graal.printer/src/com/oracle/max/graal/printer/IdealGraphPrinter.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.printer/src/com/oracle/max/graal/printer/IdealGraphPrinter.java Thu Jan 26 12:23:00 2012 +0100 @@ -29,16 +29,13 @@ import com.oracle.max.cri.ri.*; import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.schedule.*; -import com.oracle.max.graal.compiler.util.*; -import com.oracle.max.graal.compiler.util.LoopUtil.Loop; import com.oracle.max.graal.graph.*; import com.oracle.max.graal.graph.Node.Verbosity; import com.oracle.max.graal.graph.NodeClass.NodeClassIterator; import com.oracle.max.graal.graph.NodeClass.Position; import com.oracle.max.graal.java.*; import com.oracle.max.graal.nodes.*; -import com.oracle.max.graal.nodes.loop.*; -import com.oracle.max.graal.printer.BasicIdealGraphPrinter.*; +import com.oracle.max.graal.printer.BasicIdealGraphPrinter.Edge; /** * Generates a representation of {@link Graph Graphs} that can be visualized and inspected with the <a @@ -142,22 +139,9 @@ // nothing to do here... } } - List<Loop> loops = null; - try { - loops = LoopUtil.computeLoops((StructuredGraph) graph); - // loop.nodes() does some more calculations which may fail, so execute this here as well (result is cached) - if (loops != null) { - for (Loop loop : loops) { - loop.nodes(); - } - } - } catch (Throwable t) { - t.printStackTrace(); - loops = null; - } printer.beginNodes(); - List<Edge> edges = printNodes(graph, shortNames, schedule == null ? null : schedule.getNodeToBlock(), loops); + List<Edge> edges = printNodes(graph, shortNames, schedule == null ? null : schedule.getNodeToBlock()); printer.endNodes(); printer.beginEdges(); @@ -179,14 +163,8 @@ flush(); } - private List<Edge> printNodes(Graph graph, boolean shortNames, NodeMap<Block> nodeToBlock, List<Loop> loops) { + private List<Edge> printNodes(Graph graph, boolean shortNames, NodeMap<Block> nodeToBlock) { ArrayList<Edge> edges = new ArrayList<>(); - NodeBitMap loopExits = graph.createNodeBitMap(); - if (loops != null) { - for (Loop loop : loops) { - loopExits.setUnion(loop.exits()); - } - } NodeMap<Set<Entry<String, Integer>>> colors = graph.createNodeMap(); NodeMap<Set<Entry<String, String>>> colorsToString = graph.createNodeMap(); @@ -260,30 +238,13 @@ Block block = nodeToBlock == null ? null : nodeToBlock.get(node); if (block != null) { printer.printProperty("block", Integer.toString(block.blockID())); - if (!(node instanceof PhiNode || node instanceof FrameState || node instanceof LocalNode || node instanceof InductionVariableNode) && !block.getInstructions().contains(node)) { + if (!(node instanceof PhiNode || node instanceof FrameState || node instanceof LocalNode) && !block.getInstructions().contains(node)) { printer.printProperty("notInOwnBlock", "true"); } } else { printer.printProperty("block", "noBlock"); noBlockNodes.add(node); } - if (loopExits.isMarked(node)) { - printer.printProperty("loopExit", "true"); - } - StringBuilder sb = new StringBuilder(); - if (loops != null) { - for (Loop loop : loops) { - if (loop.nodes().isMarked(node)) { - if (sb.length() > 0) { - sb.append(", "); - } - sb.append(loop.loopBegin().toString(Verbosity.Id)); - } - } - } - if (sb.length() > 0) { - printer.printProperty("loops", sb.toString()); - } Set<Entry<String, Integer>> nodeColors = colors.get(node); if (nodeColors != null) { @@ -386,11 +347,6 @@ for (PhiNode phi : ((MergeNode) node).phis()) { nodes.add(phi); } - if (node instanceof LoopBeginNode) { - for (InductionVariableNode iv : ((LoopBeginNode) node).inductionVariables()) { - nodes.add(iv); - } - } } }
--- a/graal/com.oracle.max.graal.tests/src/com/oracle/max/graal/compiler/tests/NestedLoopTest.java Thu Jan 26 10:54:23 2012 +0100 +++ b/graal/com.oracle.max.graal.tests/src/com/oracle/max/graal/compiler/tests/NestedLoopTest.java Thu Jan 26 12:23:00 2012 +0100 @@ -27,98 +27,93 @@ import com.oracle.max.graal.compiler.loop.*; import com.oracle.max.graal.nodes.*; -/** - * In the following tests, the usages of local variable "a" are replaced with the integer constant 0. - * Then canonicalization is applied and it is verified that the resulting graph is equal to the - * graph of the method that just has a "return 1" statement in it. - */ public class NestedLoopTest extends GraphTest { @Test public void test1() { - test("test1Snippet"); + test("test1Snippet", 5, 5, 4); } @Test public void test2() { - test("test2Snippet"); + test("test2Snippet", 2, 5, 4); } @Test public void test3() { - test("test3Snippet"); + test("test3Snippet", 1, 5, 4); } @Test public void test4() { - test("test4Snippet"); + test("test4Snippet", 1, 6, 4); } @SuppressWarnings("all") public static void test1Snippet(int a) { - while (a()) { - m1: while (b()) { - while (c()) { - if (d()) { - break m1; + while (a()) { // a() exits root, while() exits root + m1: while (b()) { // b() exits nested & root, while() exits nested + while (c()) { // c() exits innermost & nested & root, while() exits innermost + if (d()) { // d() exits innermost & nested & root + break m1; // break exits innermost & nested } } } } - } + }// total : root = 5 exits, nested = 5, innermost = 4 @SuppressWarnings("all") public static void test2Snippet(int a) { - while (a()) { + while (a()) { // a() exits root, while() exits root try { - m1: while (b()) { - while (c()) { - if (d()) { - break m1; + m1: while (b()) { // b() exits nested, while() exits nested + while (c()) { // c() exits innermost & nested, while() exits innermost + if (d()) { // d() exits innermost & nested + break m1; // break exits innermost & nested } } } } catch (Throwable t) { } } - } + }// total : root = 2 exits, nested = 5, innermost = 4 @SuppressWarnings("all") public static void test3Snippet(int a) { - while (a == 0) { + while (a == 0) { // while() exits root try { - m1: while (b()) { - while (c()) { - if (d()) { - a(); - break m1; + m1: while (b()) { // b() exits nested, while() exits nested + while (c()) { // c() exits innermost & nested, while() exits innermost + if (d()) { // d() exits innermost & nested + a(); // a() exits nothing (already outside innermost & nested) + break m1; // break exits innermost & nested } } } } catch (Throwable t) { } } - } + }// total : root = 1 exit, nested = 5, innermost = 4 public static void test4Snippet(int a) { - while (a != 0) { + while (a != 0) { // while() exits root try { - m1: while (a != 0) { - b(); - while (c()) { - if (d()) { - break m1; + m1: while (a != 0) { // while() exits nested + b(); // b() exits nested + while (c()) { // c() exits innermost & nested, while() exits innermost + if (d()) { // d() exits innermost & nested + break m1; // break exits innermost & nested } } if (a != 2) { - a(); - throw new Exception(); + a(); // a() exits nothing (already outside innermost & nested) + throw new Exception(); // throw exits nested } } } catch (Throwable t) { } } - } + } // total : root = 1 exit, nested = 6, innermost = 4 private static boolean a() { return false; @@ -145,7 +140,7 @@ return null; } - private void test(String snippet) { + private void test(String snippet, int rootExits, int nestedExits, int innerExits) { StructuredGraph graph = parse(snippet); print(graph); LoopInfo loopInfo = LoopUtil.computeLoopInfo(graph); @@ -157,10 +152,15 @@ Invoke b = getInvoke("b", graph); Invoke c = getInvoke("c", graph); Invoke d = getInvoke("d", graph); - Assert.assertTrue(rootLoop.localContainsFixed((FixedNode) a)); - Assert.assertTrue(nestedLoop.localContainsFixed((FixedNode) b)); - Assert.assertTrue(innerMostLoop.localContainsFixed((FixedNode) c)); - Assert.assertTrue(innerMostLoop.localContainsFixed((FixedNode) d)); + Assert.assertTrue(rootLoop.containsDirectFixed((FixedNode) a)); + Assert.assertTrue(nestedLoop.containsDirectFixed((FixedNode) b)); + Assert.assertTrue(innerMostLoop.containsDirectFixed((FixedNode) c)); + Assert.assertTrue(innerMostLoop.containsDirectFixed((FixedNode) d)); + Assert.assertTrue(rootLoop.containsFixed((FixedNode) d)); + Assert.assertTrue(nestedLoop.containsFixed((FixedNode) d)); + Assert.assertEquals(rootExits, rootLoop.exits().cardinality()); + Assert.assertEquals(nestedExits, nestedLoop.exits().cardinality()); + Assert.assertEquals(innerExits, innerMostLoop.exits().cardinality()); print(graph); } }
--- a/mx/commands.py Thu Jan 26 10:54:23 2012 +0100 +++ b/mx/commands.py Thu Jan 26 12:23:00 2012 +0100 @@ -543,7 +543,7 @@ benchmarks += sanitycheck.getBootstraps() #SPECjvm2008 if ('specjvm2008' in args or 'all' in args): - benchmarks += [sanitycheck.getSPECjvm2008(True, 120, 120)] + benchmarks += [sanitycheck.getSPECjvm2008(None, True, 120, 120)] for test in benchmarks: if not results.has_key(test.group): @@ -555,7 +555,9 @@ f.write(json.dumps(results)) def specjvm2008(args): - sanitycheck.getSPECjvm2008().bench('-graal') + benchArgs = [a[1:] for a in args if a[0] == '@'] + vmArgs = [a for a in args if a[0] != '@'] + sanitycheck.getSPECjvm2008(benchArgs).bench('-graal', opts=vmArgs) def mx_init(): _vmbuild = 'product'
--- a/mx/sanitycheck.py Thu Jan 26 10:54:23 2012 +0100 +++ b/mx/sanitycheck.py Thu Jan 26 12:23:00 2012 +0100 @@ -67,7 +67,7 @@ class SanityCheckLevel: Fast, Gate, Normal, Extensive, Benchmark = range(5) -def getSPECjvm2008(skipKitValidation=False, warmupTime=None, iterationTime=None): +def getSPECjvm2008(benchArgs = None, skipKitValidation=False, warmupTime=None, iterationTime=None): specjvm2008 = mx.get_env('SPECJVM2008') if specjvm2008 is None or not exists(join(specjvm2008, 'SPECjvm2008.jar')): @@ -87,7 +87,7 @@ if skipKitValidation: opts += ['-ikv'] - return Test("SPECjvm2008", "SPECjvm2008", ['-jar', 'SPECjvm2008.jar'] + opts, [success], [error], [matcher], vmOpts=['-Xms3g'], defaultCwd=specjvm2008) + return Test("SPECjvm2008", "SPECjvm2008", ['-jar', 'SPECjvm2008.jar'] + opts + benchArgs, [success], [error], [matcher], vmOpts=['-Xms3g'], defaultCwd=specjvm2008) def getDacapos(level=SanityCheckLevel.Normal, gateBuildLevel=None, dacapoArgs=[]): checks = []