Mercurial > hg > truffle
changeset 6529:2e96dc4eb8e2
renamed package: com.oracle.graal.lir.cfg -> com.oracle.graal.nodes.cfg
line wrap: on
line diff
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Mon Oct 08 17:30:11 2012 +0200 @@ -27,8 +27,8 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; /** * Computes an ordering of the block that can be used by the linear scan register allocator
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java Mon Oct 08 17:30:11 2012 +0200 @@ -36,8 +36,8 @@ import com.oracle.graal.graph.*; import com.oracle.graal.graph.Node.Verbosity; import com.oracle.graal.java.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.PhasePlan.*;
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraphScheduleTest.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraphScheduleTest.java Mon Oct 08 17:30:11 2012 +0200 @@ -27,8 +27,8 @@ import org.junit.*; import com.oracle.graal.graph.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.schedule.*; public class GraphScheduleTest extends GraalCompilerTest {
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/NestedLoopTest.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/NestedLoopTest.java Mon Oct 08 17:30:11 2012 +0200 @@ -26,8 +26,8 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; public class NestedLoopTest extends GraalCompilerTest {
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SimpleCFGTest.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SimpleCFGTest.java Mon Oct 08 17:30:11 2012 +0200 @@ -26,8 +26,8 @@ import org.junit.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; public class SimpleCFGTest {
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/TypeSystemTest.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/TypeSystemTest.java Mon Oct 08 17:30:11 2012 +0200 @@ -31,8 +31,8 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.graph.Node.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.phases.common.*; import com.oracle.graal.phases.schedule.*;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon Oct 08 17:30:11 2012 +0200 @@ -35,9 +35,9 @@ import com.oracle.graal.debug.*; import com.oracle.graal.lir.*; import com.oracle.graal.lir.asm.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.loop.phases.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.PhasePlan.*;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java Mon Oct 08 17:30:11 2012 +0200 @@ -43,7 +43,7 @@ import com.oracle.graal.lir.LIRInstruction.StateProcedure; import com.oracle.graal.lir.LIRInstruction.ValueProcedure; import com.oracle.graal.lir.StandardOp.MoveOp; -import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.util.*;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java Mon Oct 08 17:30:11 2012 +0200 @@ -38,7 +38,7 @@ import com.oracle.graal.debug.*; import com.oracle.graal.lir.*; import com.oracle.graal.lir.StandardOp.*; -import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.util.*;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/RegisterVerifier.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/RegisterVerifier.java Mon Oct 08 17:30:11 2012 +0200 @@ -32,7 +32,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.lir.*; import com.oracle.graal.lir.LIRInstruction.*; -import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.util.*;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Mon Oct 08 17:30:11 2012 +0200 @@ -38,10 +38,10 @@ import com.oracle.graal.lir.StandardOp.JumpOp; import com.oracle.graal.lir.StandardOp.LabelOp; import com.oracle.graal.lir.StandardOp.ParametersOp; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.PhiNode.PhiType; import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ControlFlowOptimizer.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ControlFlowOptimizer.java Mon Oct 08 17:30:11 2012 +0200 @@ -25,7 +25,7 @@ import java.util.*; import com.oracle.graal.debug.*; -import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.cfg.*; /** * This class performs basic optimizations on the control flow graph after LIR generation.
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/EdgeMoveOptimizer.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/EdgeMoveOptimizer.java Mon Oct 08 17:30:11 2012 +0200 @@ -25,7 +25,7 @@ import java.util.*; import com.oracle.graal.lir.StandardOp.*; -import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.cfg.*; /** * This class optimizes moves, particularly those that result from eliminating SSA form.
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java Mon Oct 08 17:30:11 2012 +0200 @@ -28,8 +28,8 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.lir.asm.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; /** * This class implements the overall container for the LIR graph
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRVerifier.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRVerifier.java Mon Oct 08 17:30:11 2012 +0200 @@ -32,7 +32,7 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.lir.LIRInstruction.*; -import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.cfg.*; public final class LIRVerifier { private final LIR lir;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LabelRef.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LabelRef.java Mon Oct 08 17:30:11 2012 +0200 @@ -23,7 +23,7 @@ package com.oracle.graal.lir; import com.oracle.max.asm.*; -import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.cfg.*; /** * LIR instructions such as JUMP and BRANCH need to reference their target {@link Block}. However,
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java Mon Oct 08 17:30:11 2012 +0200 @@ -28,9 +28,9 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.graph.iterators.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.cfg.*; public class LoopEx { private final Loop lirLoop;
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java Mon Oct 08 17:30:11 2012 +0200 @@ -27,11 +27,11 @@ import com.oracle.graal.graph.*; import com.oracle.graal.graph.Graph.DuplicationReplacement; import com.oracle.graal.graph.iterators.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.PhiNode.PhiType; import com.oracle.graal.nodes.VirtualState.NodeClosure; import com.oracle.graal.nodes.VirtualState.VirtualClosure; +import com.oracle.graal.nodes.cfg.*; public abstract class LoopFragment {
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentWhole.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentWhole.java Mon Oct 08 17:30:11 2012 +0200 @@ -25,8 +25,8 @@ import com.oracle.graal.graph.Graph.DuplicationReplacement; import com.oracle.graal.graph.*; import com.oracle.graal.graph.iterators.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; public class LoopFragmentWhole extends LoopFragment {
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Mon Oct 08 17:30:11 2012 +0200 @@ -23,8 +23,8 @@ package com.oracle.graal.loop; import com.oracle.graal.debug.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.*;
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java Mon Oct 08 17:30:11 2012 +0200 @@ -27,10 +27,10 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.loop.InductionVariable.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.cfg.*; public class LoopsData { private Map<Loop, LoopEx> lirLoopToEx = new IdentityHashMap<>();
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/lir/cfg/Block.java Mon Oct 08 17:18:31 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,210 +0,0 @@ -/* - * Copyright (c) 2009, 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.cfg; - -import java.util.*; - -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.java.*; - -public class Block { - - protected int id; - - protected BeginNode beginNode; - protected FixedNode endNode; - protected Loop loop; - protected double probability; - - protected List<Block> predecessors; - protected List<Block> successors; - - protected Block dominator; - protected List<Block> dominated; - protected Block postdominator; - - // Fields that still need to be worked on, try to remove them later. - public boolean align; - public int linearScanNumber; - - protected Block() { - id = ControlFlowGraph.BLOCK_ID_INITIAL; - } - - public int getId() { - return id; - } - - public BeginNode getBeginNode() { - return beginNode; - } - - public FixedNode getEndNode() { - return endNode; - } - - public Loop getLoop() { - return loop; - } - - public int getLoopDepth() { - return loop == null ? 0 : loop.depth; - } - - public boolean isLoopHeader() { - return getBeginNode() instanceof LoopBeginNode; - } - - public boolean isLoopEnd() { - return getEndNode() instanceof LoopEndNode; - } - - public boolean isExceptionEntry() { - return getBeginNode().next() instanceof ExceptionObjectNode; - } - - public List<Block> getPredecessors() { - return predecessors; - } - - public List<Block> getSuccessors() { - return successors; - } - - public Block getDominator() { - return dominator; - } - - public Block getEarliestPostDominated() { - Block b = this; - while (true) { - Block dom = b.getDominator(); - if (dom != null && dom.getPostdominator() == b) { - b = dom; - } else { - break; - } - } - return b; - } - - public List<Block> getDominated() { - if (dominated == null) { - return Collections.emptyList(); - } - return dominated; - } - - public Block getPostdominator() { - return postdominator; - } - - private class NodeIterator implements Iterator<FixedNode> { - private FixedNode cur; - - public NodeIterator() { - cur = getBeginNode(); - } - - @Override - public boolean hasNext() { - return cur != null; - } - - @Override - public FixedNode next() { - FixedNode result = cur; - if (cur == getEndNode()) { - cur = null; - } else { - cur = ((FixedWithNextNode) cur).next(); - } - assert !(cur instanceof BeginNode); - return result; - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - } - - public Iterable<FixedNode> getNodes() { - return new Iterable<FixedNode>() { - @Override - public Iterator<FixedNode> iterator() { - return new NodeIterator(); - } - - @Override - public String toString() { - StringBuilder str = new StringBuilder().append('['); - for (FixedNode node : this) { - str.append(node).append(", "); - } - if (str.length() > 1) { - str.setLength(str.length() - 2); - } - return str.append(']').toString(); - } - }; - } - - @Override - public String toString() { - return "B" + id; - } - - -// to be inlined later on - public int numberOfPreds() { - return getPredecessors().size(); - } - - public int numberOfSux() { - return getSuccessors().size(); - } - - public Block predAt(int i) { - return getPredecessors().get(i); - } - - public Block suxAt(int i) { - return getSuccessors().get(i); - } -// end to be inlined later on - - public boolean dominates(Block block) { - return block.isDominatedBy(this); - } - - public boolean isDominatedBy(Block block) { - if (block == this) { - return true; - } - if (dominator == null) { - return false; - } - return dominator.isDominatedBy(block); - } -}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/lir/cfg/BlockMap.java Mon Oct 08 17:18:31 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,40 +0,0 @@ -/* - * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.cfg; - -public class BlockMap<T> { - private final T[] data; - - @SuppressWarnings("unchecked") - public BlockMap(ControlFlowGraph cfg) { - data = (T[]) new Object[cfg.getBlocks().length]; - } - - public T get(Block block) { - return data[block.getId()]; - } - - public void put(Block block, T value) { - data[block.getId()] = value; - } -}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/lir/cfg/CFGVerifier.java Mon Oct 08 17:18:31 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,89 +0,0 @@ -/* - * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.cfg; - -public class CFGVerifier { - public static boolean verify(ControlFlowGraph cfg) { - for (Block block : cfg.getBlocks()) { - assert block.getId() >= 0; - assert cfg.getBlocks()[block.getId()] == block; - - for (Block pred : block.getPredecessors()) { - assert pred.getSuccessors().contains(block); - assert pred.getId() < block.getId() || pred.isLoopEnd(); - } - - for (Block sux : block.getSuccessors()) { - assert sux.getPredecessors().contains(block); - assert sux.getId() > block.getId() || sux.isLoopHeader(); - } - - if (block.getDominator() != null) { - assert block.getDominator().getId() < block.getId(); - assert block.getDominator().getDominated().contains(block); - } - for (Block dominated : block.getDominated()) { - assert dominated.getId() > block.getId(); - assert dominated.getDominator() == block; - } - - assert cfg.getLoops() == null || !block.isLoopHeader() || block.getLoop().header == block : block.beginNode; - } - - if (cfg.getLoops() != null) { - for (Loop loop : cfg.getLoops()) { - assert loop.header.isLoopHeader(); - - for (Block block : loop.blocks) { - assert block.getId() >= loop.header.getId(); - - Loop blockLoop = block.getLoop(); - while (blockLoop != loop) { - assert blockLoop != null; - blockLoop = blockLoop.parent; - } - - if (!(block.isLoopHeader() && block.getLoop() == loop)) { - for (Block pred : block.getPredecessors()) { - if (!loop.blocks.contains(pred)) { - return false; - } - } - } - } - - for (Block block : loop.exits) { - assert block.getId() >= loop.header.getId(); - - Loop blockLoop = block.getLoop(); - while (blockLoop != null) { - blockLoop = blockLoop.parent; - assert blockLoop != loop; - } - } - } - } - - return true; - } -}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/lir/cfg/ControlFlowGraph.java Mon Oct 08 17:18:31 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,368 +0,0 @@ -/* - * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.cfg; - -import java.util.*; - -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; - -public class ControlFlowGraph { - - public final StructuredGraph graph; - - private final NodeMap<Block> nodeToBlock; - private Block[] reversePostOrder; - private Loop[] loops; - - - public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) { - ControlFlowGraph cfg = new ControlFlowGraph(graph); - cfg.identifyBlocks(); - if (connectBlocks || computeLoops || computeDominators || computePostdominators) { - cfg.connectBlocks(); - } - if (computeLoops) { - cfg.computeLoopInformation(); - } - if (computeDominators) { - cfg.computeDominators(); - } - if (computePostdominators) { - cfg.computePostdominators(); - } - assert CFGVerifier.verify(cfg); - return cfg; - } - - protected ControlFlowGraph(StructuredGraph graph) { - this.graph = graph; - this.nodeToBlock = graph.createNodeMap(); - } - - public Block[] getBlocks() { - return reversePostOrder; - } - - public Block getStartBlock() { - return reversePostOrder[0]; - } - - public Iterable<Block> postOrder() { - return new Iterable<Block>() { - @Override - public Iterator<Block> iterator() { - return new Iterator<Block>() { - private int nextIndex = reversePostOrder.length - 1; - @Override - public boolean hasNext() { - return nextIndex >= 0; - } - - @Override - public Block next() { - return reversePostOrder[nextIndex--]; - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - }; - } - }; - } - - public NodeMap<Block> getNodeToBlock() { - return nodeToBlock; - } - - public Block blockFor(Node node) { - return nodeToBlock.get(node); - } - - public Loop[] getLoops() { - return loops; - } - - protected static final int BLOCK_ID_INITIAL = -1; - protected static final int BLOCK_ID_VISITED = -2; - - private void identifyBlocks() { - // Find all block headers - int numBlocks = 0; - for (Node node : graph.getNodes()) { - if (node instanceof BeginNode) { - Block block = new Block(); - numBlocks++; - - block.beginNode = (BeginNode) node; - Node cur = node; - Node last; - do { - assert !cur.isDeleted(); - - assert nodeToBlock.get(cur) == null; - nodeToBlock.set(cur, block); - if (cur instanceof MergeNode) { - for (PhiNode phi : ((MergeNode) cur).phis()) { - nodeToBlock.set(phi, block); - } - } - - if (cur instanceof FixedNode) { - double probability = ((FixedNode) cur).probability(); - if (probability > block.probability) { - block.probability = probability; - } - } - - last = cur; - cur = cur.successors().first(); - } while (cur != null && !(cur instanceof BeginNode)); - - block.endNode = (FixedNode) last; - } - } - - // Compute postorder. - ArrayList<Block> postOrder = new ArrayList<>(numBlocks); - ArrayList<Block> stack = new ArrayList<>(); - stack.add(blockFor(graph.start())); - - do { - Block block = stack.get(stack.size() - 1); - if (block.id == BLOCK_ID_INITIAL) { - // First time we see this block: push all successors. - for (Node suxNode : block.getEndNode().cfgSuccessors()) { - Block suxBlock = blockFor(suxNode); - if (suxBlock.id == BLOCK_ID_INITIAL) { - stack.add(suxBlock); - } - } - block.id = BLOCK_ID_VISITED; - } else if (block.id == BLOCK_ID_VISITED) { - // Second time we see this block: All successors have been processed, so add block to postorder list. - stack.remove(stack.size() - 1); - postOrder.add(block); - } else { - throw GraalInternalError.shouldNotReachHere(); - } - } while (!stack.isEmpty()); - - // Compute reverse postorder and number blocks. - assert postOrder.size() <= numBlocks : "some blocks originally created can be unreachable, so actual block list can be shorter"; - numBlocks = postOrder.size(); - reversePostOrder = new Block[numBlocks]; - for (int i = 0; i < numBlocks; i++) { - Block block = postOrder.get(numBlocks - i - 1); - block.id = i; - reversePostOrder[i] = block; - } - } - - // Connect blocks (including loop backward edges), but ignoring dead code (blocks with id < 0). - private void connectBlocks() { - for (Block block : reversePostOrder) { - List<Block> predecessors = new ArrayList<>(); - for (Node predNode : block.getBeginNode().cfgPredecessors()) { - Block predBlock = nodeToBlock.get(predNode); - if (predBlock.id >= 0) { - predecessors.add(predBlock); - } - } - if (block.getBeginNode() instanceof LoopBeginNode) { - for (LoopEndNode predNode : ((LoopBeginNode) block.getBeginNode()).orderedLoopEnds()) { - Block predBlock = nodeToBlock.get(predNode); - if (predBlock.id >= 0) { - predecessors.add(predBlock); - } - } - } - block.predecessors = predecessors; - - List<Block> successors = new ArrayList<>(); - for (Node suxNode : block.getEndNode().cfgSuccessors()) { - Block suxBlock = nodeToBlock.get(suxNode); - assert suxBlock.id >= 0; - successors.add(suxBlock); - } - if (block.getEndNode() instanceof LoopEndNode) { - Block suxBlock = nodeToBlock.get(((LoopEndNode) block.getEndNode()).loopBegin()); - assert suxBlock.id >= 0; - successors.add(suxBlock); - } - block.successors = successors; - } - } - - private void computeLoopInformation() { - ArrayList<Loop> loopsList = new ArrayList<>(); - for (Block block : reversePostOrder) { - Node beginNode = block.getBeginNode(); - if (beginNode instanceof LoopBeginNode) { - Loop loop = new Loop(block.getLoop(), loopsList.size(), block); - loopsList.add(loop); - - LoopBeginNode loopBegin = (LoopBeginNode) beginNode; - for (LoopEndNode end : loopBegin.loopEnds()) { - Block endBlock = nodeToBlock.get(end); - computeLoopBlocks(endBlock, loop); - } - - for (LoopExitNode exit : loopBegin.loopExits()) { - Block exitBlock = nodeToBlock.get(exit); - List<Block> predecessors = exitBlock.getPredecessors(); - assert predecessors.size() == 1; - computeLoopBlocks(predecessors.get(0), loop); - loop.exits.add(exitBlock); - } - List<Block> unexpected = new LinkedList<>(); - for (Block b : loop.blocks) { - for (Block sux : b.getSuccessors()) { - if (sux.loop != loop) { - BeginNode begin = sux.getBeginNode(); - if (!(begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == loopBegin)) { - Debug.log("Unexpected loop exit with %s, including whole branch in the loop", sux); - unexpected.add(sux); - } - } - } - } - for (Block b : unexpected) { - addBranchToLoop(loop, b); - } - } - } - loops = loopsList.toArray(new Loop[loopsList.size()]); - } - - private static void addBranchToLoop(Loop l, Block b) { - if (l.blocks.contains(b)) { - return; - } - l.blocks.add(b); - b.loop = l; - for (Block sux : b.getSuccessors()) { - addBranchToLoop(l, sux); - } - } - - private static void computeLoopBlocks(Block block, Loop loop) { - if (block.getLoop() == loop) { - return; - } - assert block.loop == loop.parent; - block.loop = loop; - - assert !loop.blocks.contains(block); - loop.blocks.add(block); - - if (block != loop.header) { - for (Block pred : block.getPredecessors()) { - computeLoopBlocks(pred, loop); - } - } - } - - private void computeDominators() { - assert reversePostOrder[0].getPredecessors().size() == 0 : "start block has no predecessor and therefore no dominator"; - for (int i = 1; i < reversePostOrder.length; i++) { - Block block = reversePostOrder[i]; - List<Block> predecessors = block.getPredecessors(); - assert predecessors.size() > 0; - - Block dominator = predecessors.get(0); - for (int j = 1; j < predecessors.size(); j++) { - Block pred = predecessors.get(j); - if (!pred.isLoopEnd()) { - dominator = commonDominator(dominator, pred); - } - } - setDominator(block, dominator); - } - } - - private static void setDominator(Block block, Block dominator) { - block.dominator = dominator; - if (dominator.dominated == null) { - dominator.dominated = new ArrayList<>(); - } - dominator.dominated.add(block); - } - - public static Block commonDominator(Block a, Block b) { - Block iterA = a; - Block iterB = b; - while (iterA != iterB) { - if (iterA.getId() > iterB.getId()) { - iterA = iterA.getDominator(); - } else { - assert iterB.getId() > iterA.getId(); - iterB = iterB.getDominator(); - } - } - return iterA; - } - - private void computePostdominators() { - for (Block block : postOrder()) { - if (block.isLoopEnd()) { - // We do not want the loop header registered as the postdominator of the loop end. - continue; - } - Block postdominator = null; - for (Block sux : block.getSuccessors()) { - if (sux.isExceptionEntry()) { - // We ignore exception handlers. - } else if (postdominator == null) { - postdominator = sux; - } else { - postdominator = commonPostdominator(postdominator, sux); - } - } - block.postdominator = postdominator; - } - } - - private static Block commonPostdominator(Block a, Block b) { - Block iterA = a; - Block iterB = b; - while (iterA != iterB) { - if (iterA.getId() < iterB.getId()) { - iterA = iterA.getPostdominator(); - if (iterA == null) { - return null; - } - } else { - assert iterB.getId() < iterA.getId(); - iterB = iterB.getPostdominator(); - if (iterB == null) { - return null; - } - } - } - return iterA; - } -}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/lir/cfg/Loop.java Mon Oct 08 17:18:31 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,63 +0,0 @@ -/* - * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.cfg; - -import java.util.*; - -import com.oracle.graal.nodes.*; - -public class Loop { - - public final Loop parent; - public final List<Loop> children; - - public final int depth; - public final int index; - public final Block header; - public final List<Block> blocks; - public final List<Block> exits; - - protected Loop(Loop parent, int index, Block header) { - this.parent = parent; - if (parent != null) { - this.depth = parent.depth + 1; - parent.children.add(this); - } else { - this.depth = 1; - } - this.index = index; - this.header = header; - this.blocks = new ArrayList<>(); - this.children = new ArrayList<>(); - this.exits = new ArrayList<>(); - } - - @Override - public String toString() { - return "loop " + index + " depth " + depth + (parent != null ? " outer " + parent.index : ""); - } - - public LoopBeginNode loopBegin() { - return (LoopBeginNode) header.getBeginNode(); - } -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Mon Oct 08 17:30:11 2012 +0200 @@ -0,0 +1,210 @@ +/* + * Copyright (c) 2009, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes.cfg; + +import java.util.*; + +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.java.*; + +public class Block { + + protected int id; + + protected BeginNode beginNode; + protected FixedNode endNode; + protected Loop loop; + protected double probability; + + protected List<Block> predecessors; + protected List<Block> successors; + + protected Block dominator; + protected List<Block> dominated; + protected Block postdominator; + + // Fields that still need to be worked on, try to remove them later. + public boolean align; + public int linearScanNumber; + + protected Block() { + id = ControlFlowGraph.BLOCK_ID_INITIAL; + } + + public int getId() { + return id; + } + + public BeginNode getBeginNode() { + return beginNode; + } + + public FixedNode getEndNode() { + return endNode; + } + + public Loop getLoop() { + return loop; + } + + public int getLoopDepth() { + return loop == null ? 0 : loop.depth; + } + + public boolean isLoopHeader() { + return getBeginNode() instanceof LoopBeginNode; + } + + public boolean isLoopEnd() { + return getEndNode() instanceof LoopEndNode; + } + + public boolean isExceptionEntry() { + return getBeginNode().next() instanceof ExceptionObjectNode; + } + + public List<Block> getPredecessors() { + return predecessors; + } + + public List<Block> getSuccessors() { + return successors; + } + + public Block getDominator() { + return dominator; + } + + public Block getEarliestPostDominated() { + Block b = this; + while (true) { + Block dom = b.getDominator(); + if (dom != null && dom.getPostdominator() == b) { + b = dom; + } else { + break; + } + } + return b; + } + + public List<Block> getDominated() { + if (dominated == null) { + return Collections.emptyList(); + } + return dominated; + } + + public Block getPostdominator() { + return postdominator; + } + + private class NodeIterator implements Iterator<FixedNode> { + private FixedNode cur; + + public NodeIterator() { + cur = getBeginNode(); + } + + @Override + public boolean hasNext() { + return cur != null; + } + + @Override + public FixedNode next() { + FixedNode result = cur; + if (cur == getEndNode()) { + cur = null; + } else { + cur = ((FixedWithNextNode) cur).next(); + } + assert !(cur instanceof BeginNode); + return result; + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + } + + public Iterable<FixedNode> getNodes() { + return new Iterable<FixedNode>() { + @Override + public Iterator<FixedNode> iterator() { + return new NodeIterator(); + } + + @Override + public String toString() { + StringBuilder str = new StringBuilder().append('['); + for (FixedNode node : this) { + str.append(node).append(", "); + } + if (str.length() > 1) { + str.setLength(str.length() - 2); + } + return str.append(']').toString(); + } + }; + } + + @Override + public String toString() { + return "B" + id; + } + + +// to be inlined later on + public int numberOfPreds() { + return getPredecessors().size(); + } + + public int numberOfSux() { + return getSuccessors().size(); + } + + public Block predAt(int i) { + return getPredecessors().get(i); + } + + public Block suxAt(int i) { + return getSuccessors().get(i); + } +// end to be inlined later on + + public boolean dominates(Block block) { + return block.isDominatedBy(this); + } + + public boolean isDominatedBy(Block block) { + if (block == this) { + return true; + } + if (dominator == null) { + return false; + } + return dominator.isDominatedBy(block); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/BlockMap.java Mon Oct 08 17:30:11 2012 +0200 @@ -0,0 +1,40 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes.cfg; + +public class BlockMap<T> { + private final T[] data; + + @SuppressWarnings("unchecked") + public BlockMap(ControlFlowGraph cfg) { + data = (T[]) new Object[cfg.getBlocks().length]; + } + + public T get(Block block) { + return data[block.getId()]; + } + + public void put(Block block, T value) { + data[block.getId()] = value; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/CFGVerifier.java Mon Oct 08 17:30:11 2012 +0200 @@ -0,0 +1,89 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes.cfg; + +public class CFGVerifier { + public static boolean verify(ControlFlowGraph cfg) { + for (Block block : cfg.getBlocks()) { + assert block.getId() >= 0; + assert cfg.getBlocks()[block.getId()] == block; + + for (Block pred : block.getPredecessors()) { + assert pred.getSuccessors().contains(block); + assert pred.getId() < block.getId() || pred.isLoopEnd(); + } + + for (Block sux : block.getSuccessors()) { + assert sux.getPredecessors().contains(block); + assert sux.getId() > block.getId() || sux.isLoopHeader(); + } + + if (block.getDominator() != null) { + assert block.getDominator().getId() < block.getId(); + assert block.getDominator().getDominated().contains(block); + } + for (Block dominated : block.getDominated()) { + assert dominated.getId() > block.getId(); + assert dominated.getDominator() == block; + } + + assert cfg.getLoops() == null || !block.isLoopHeader() || block.getLoop().header == block : block.beginNode; + } + + if (cfg.getLoops() != null) { + for (Loop loop : cfg.getLoops()) { + assert loop.header.isLoopHeader(); + + for (Block block : loop.blocks) { + assert block.getId() >= loop.header.getId(); + + Loop blockLoop = block.getLoop(); + while (blockLoop != loop) { + assert blockLoop != null; + blockLoop = blockLoop.parent; + } + + if (!(block.isLoopHeader() && block.getLoop() == loop)) { + for (Block pred : block.getPredecessors()) { + if (!loop.blocks.contains(pred)) { + return false; + } + } + } + } + + for (Block block : loop.exits) { + assert block.getId() >= loop.header.getId(); + + Loop blockLoop = block.getLoop(); + while (blockLoop != null) { + blockLoop = blockLoop.parent; + assert blockLoop != loop; + } + } + } + } + + return true; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Mon Oct 08 17:30:11 2012 +0200 @@ -0,0 +1,368 @@ +/* + * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes.cfg; + +import java.util.*; + +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; + +public class ControlFlowGraph { + + public final StructuredGraph graph; + + private final NodeMap<Block> nodeToBlock; + private Block[] reversePostOrder; + private Loop[] loops; + + + public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) { + ControlFlowGraph cfg = new ControlFlowGraph(graph); + cfg.identifyBlocks(); + if (connectBlocks || computeLoops || computeDominators || computePostdominators) { + cfg.connectBlocks(); + } + if (computeLoops) { + cfg.computeLoopInformation(); + } + if (computeDominators) { + cfg.computeDominators(); + } + if (computePostdominators) { + cfg.computePostdominators(); + } + assert CFGVerifier.verify(cfg); + return cfg; + } + + protected ControlFlowGraph(StructuredGraph graph) { + this.graph = graph; + this.nodeToBlock = graph.createNodeMap(); + } + + public Block[] getBlocks() { + return reversePostOrder; + } + + public Block getStartBlock() { + return reversePostOrder[0]; + } + + public Iterable<Block> postOrder() { + return new Iterable<Block>() { + @Override + public Iterator<Block> iterator() { + return new Iterator<Block>() { + private int nextIndex = reversePostOrder.length - 1; + @Override + public boolean hasNext() { + return nextIndex >= 0; + } + + @Override + public Block next() { + return reversePostOrder[nextIndex--]; + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + }; + } + }; + } + + public NodeMap<Block> getNodeToBlock() { + return nodeToBlock; + } + + public Block blockFor(Node node) { + return nodeToBlock.get(node); + } + + public Loop[] getLoops() { + return loops; + } + + protected static final int BLOCK_ID_INITIAL = -1; + protected static final int BLOCK_ID_VISITED = -2; + + private void identifyBlocks() { + // Find all block headers + int numBlocks = 0; + for (Node node : graph.getNodes()) { + if (node instanceof BeginNode) { + Block block = new Block(); + numBlocks++; + + block.beginNode = (BeginNode) node; + Node cur = node; + Node last; + do { + assert !cur.isDeleted(); + + assert nodeToBlock.get(cur) == null; + nodeToBlock.set(cur, block); + if (cur instanceof MergeNode) { + for (PhiNode phi : ((MergeNode) cur).phis()) { + nodeToBlock.set(phi, block); + } + } + + if (cur instanceof FixedNode) { + double probability = ((FixedNode) cur).probability(); + if (probability > block.probability) { + block.probability = probability; + } + } + + last = cur; + cur = cur.successors().first(); + } while (cur != null && !(cur instanceof BeginNode)); + + block.endNode = (FixedNode) last; + } + } + + // Compute postorder. + ArrayList<Block> postOrder = new ArrayList<>(numBlocks); + ArrayList<Block> stack = new ArrayList<>(); + stack.add(blockFor(graph.start())); + + do { + Block block = stack.get(stack.size() - 1); + if (block.id == BLOCK_ID_INITIAL) { + // First time we see this block: push all successors. + for (Node suxNode : block.getEndNode().cfgSuccessors()) { + Block suxBlock = blockFor(suxNode); + if (suxBlock.id == BLOCK_ID_INITIAL) { + stack.add(suxBlock); + } + } + block.id = BLOCK_ID_VISITED; + } else if (block.id == BLOCK_ID_VISITED) { + // Second time we see this block: All successors have been processed, so add block to postorder list. + stack.remove(stack.size() - 1); + postOrder.add(block); + } else { + throw GraalInternalError.shouldNotReachHere(); + } + } while (!stack.isEmpty()); + + // Compute reverse postorder and number blocks. + assert postOrder.size() <= numBlocks : "some blocks originally created can be unreachable, so actual block list can be shorter"; + numBlocks = postOrder.size(); + reversePostOrder = new Block[numBlocks]; + for (int i = 0; i < numBlocks; i++) { + Block block = postOrder.get(numBlocks - i - 1); + block.id = i; + reversePostOrder[i] = block; + } + } + + // Connect blocks (including loop backward edges), but ignoring dead code (blocks with id < 0). + private void connectBlocks() { + for (Block block : reversePostOrder) { + List<Block> predecessors = new ArrayList<>(); + for (Node predNode : block.getBeginNode().cfgPredecessors()) { + Block predBlock = nodeToBlock.get(predNode); + if (predBlock.id >= 0) { + predecessors.add(predBlock); + } + } + if (block.getBeginNode() instanceof LoopBeginNode) { + for (LoopEndNode predNode : ((LoopBeginNode) block.getBeginNode()).orderedLoopEnds()) { + Block predBlock = nodeToBlock.get(predNode); + if (predBlock.id >= 0) { + predecessors.add(predBlock); + } + } + } + block.predecessors = predecessors; + + List<Block> successors = new ArrayList<>(); + for (Node suxNode : block.getEndNode().cfgSuccessors()) { + Block suxBlock = nodeToBlock.get(suxNode); + assert suxBlock.id >= 0; + successors.add(suxBlock); + } + if (block.getEndNode() instanceof LoopEndNode) { + Block suxBlock = nodeToBlock.get(((LoopEndNode) block.getEndNode()).loopBegin()); + assert suxBlock.id >= 0; + successors.add(suxBlock); + } + block.successors = successors; + } + } + + private void computeLoopInformation() { + ArrayList<Loop> loopsList = new ArrayList<>(); + for (Block block : reversePostOrder) { + Node beginNode = block.getBeginNode(); + if (beginNode instanceof LoopBeginNode) { + Loop loop = new Loop(block.getLoop(), loopsList.size(), block); + loopsList.add(loop); + + LoopBeginNode loopBegin = (LoopBeginNode) beginNode; + for (LoopEndNode end : loopBegin.loopEnds()) { + Block endBlock = nodeToBlock.get(end); + computeLoopBlocks(endBlock, loop); + } + + for (LoopExitNode exit : loopBegin.loopExits()) { + Block exitBlock = nodeToBlock.get(exit); + List<Block> predecessors = exitBlock.getPredecessors(); + assert predecessors.size() == 1; + computeLoopBlocks(predecessors.get(0), loop); + loop.exits.add(exitBlock); + } + List<Block> unexpected = new LinkedList<>(); + for (Block b : loop.blocks) { + for (Block sux : b.getSuccessors()) { + if (sux.loop != loop) { + BeginNode begin = sux.getBeginNode(); + if (!(begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == loopBegin)) { + Debug.log("Unexpected loop exit with %s, including whole branch in the loop", sux); + unexpected.add(sux); + } + } + } + } + for (Block b : unexpected) { + addBranchToLoop(loop, b); + } + } + } + loops = loopsList.toArray(new Loop[loopsList.size()]); + } + + private static void addBranchToLoop(Loop l, Block b) { + if (l.blocks.contains(b)) { + return; + } + l.blocks.add(b); + b.loop = l; + for (Block sux : b.getSuccessors()) { + addBranchToLoop(l, sux); + } + } + + private static void computeLoopBlocks(Block block, Loop loop) { + if (block.getLoop() == loop) { + return; + } + assert block.loop == loop.parent; + block.loop = loop; + + assert !loop.blocks.contains(block); + loop.blocks.add(block); + + if (block != loop.header) { + for (Block pred : block.getPredecessors()) { + computeLoopBlocks(pred, loop); + } + } + } + + private void computeDominators() { + assert reversePostOrder[0].getPredecessors().size() == 0 : "start block has no predecessor and therefore no dominator"; + for (int i = 1; i < reversePostOrder.length; i++) { + Block block = reversePostOrder[i]; + List<Block> predecessors = block.getPredecessors(); + assert predecessors.size() > 0; + + Block dominator = predecessors.get(0); + for (int j = 1; j < predecessors.size(); j++) { + Block pred = predecessors.get(j); + if (!pred.isLoopEnd()) { + dominator = commonDominator(dominator, pred); + } + } + setDominator(block, dominator); + } + } + + private static void setDominator(Block block, Block dominator) { + block.dominator = dominator; + if (dominator.dominated == null) { + dominator.dominated = new ArrayList<>(); + } + dominator.dominated.add(block); + } + + public static Block commonDominator(Block a, Block b) { + Block iterA = a; + Block iterB = b; + while (iterA != iterB) { + if (iterA.getId() > iterB.getId()) { + iterA = iterA.getDominator(); + } else { + assert iterB.getId() > iterA.getId(); + iterB = iterB.getDominator(); + } + } + return iterA; + } + + private void computePostdominators() { + for (Block block : postOrder()) { + if (block.isLoopEnd()) { + // We do not want the loop header registered as the postdominator of the loop end. + continue; + } + Block postdominator = null; + for (Block sux : block.getSuccessors()) { + if (sux.isExceptionEntry()) { + // We ignore exception handlers. + } else if (postdominator == null) { + postdominator = sux; + } else { + postdominator = commonPostdominator(postdominator, sux); + } + } + block.postdominator = postdominator; + } + } + + private static Block commonPostdominator(Block a, Block b) { + Block iterA = a; + Block iterB = b; + while (iterA != iterB) { + if (iterA.getId() < iterB.getId()) { + iterA = iterA.getPostdominator(); + if (iterA == null) { + return null; + } + } else { + assert iterB.getId() < iterA.getId(); + iterB = iterB.getPostdominator(); + if (iterB == null) { + return null; + } + } + } + return iterA; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Loop.java Mon Oct 08 17:30:11 2012 +0200 @@ -0,0 +1,63 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes.cfg; + +import java.util.*; + +import com.oracle.graal.nodes.*; + +public class Loop { + + public final Loop parent; + public final List<Loop> children; + + public final int depth; + public final int index; + public final Block header; + public final List<Block> blocks; + public final List<Block> exits; + + protected Loop(Loop parent, int index, Block header) { + this.parent = parent; + if (parent != null) { + this.depth = parent.depth + 1; + parent.children.add(this); + } else { + this.depth = 1; + } + this.index = index; + this.header = header; + this.blocks = new ArrayList<>(); + this.children = new ArrayList<>(); + this.exits = new ArrayList<>(); + } + + @Override + public String toString() { + return "loop " + index + " depth " + depth + (parent != null ? " outer " + parent.index : ""); + } + + public LoopBeginNode loopBegin() { + return (LoopBeginNode) header.getBeginNode(); + } +}
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityPhase.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityPhase.java Mon Oct 08 17:30:11 2012 +0200 @@ -26,8 +26,8 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.graph.*;
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java Mon Oct 08 17:30:11 2012 +0200 @@ -29,9 +29,9 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.graph.iterators.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.schedule.*;
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/BlockClosure.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/BlockClosure.java Mon Oct 08 17:30:11 2012 +0200 @@ -22,7 +22,7 @@ */ package com.oracle.graal.phases.schedule; -import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.cfg.*; /** * The {@code BlockClosure} interface represents a closure for iterating over blocks.
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Mon Oct 08 17:30:11 2012 +0200 @@ -27,8 +27,8 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.graph.Node.Verbosity; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.virtual.*; import com.oracle.graal.phases.*;
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java Mon Oct 08 17:30:11 2012 +0200 @@ -32,8 +32,8 @@ import com.oracle.graal.graph.*; import com.oracle.graal.graph.NodeClass.NodeClassIterator; import com.oracle.graal.graph.NodeClass.Position; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.schedule.*; public class BinaryGraphPrinter implements GraphPrinter{
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Mon Oct 08 17:30:11 2012 +0200 @@ -38,9 +38,9 @@ import com.oracle.graal.graph.NodeClass.Position; import com.oracle.graal.java.*; import com.oracle.graal.lir.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.cfg.*; /** * Utility for printing Graal IR at various compilation phases.
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java Mon Oct 08 17:30:11 2012 +0200 @@ -35,8 +35,8 @@ import com.oracle.graal.graph.*; import com.oracle.graal.java.*; import com.oracle.graal.lir.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; /** * Observes compilation events and uses {@link CFGPrinter} to produce a control flow graph for the <a
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/IdealGraphPrinter.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/IdealGraphPrinter.java Mon Oct 08 17:30:11 2012 +0200 @@ -32,8 +32,8 @@ import com.oracle.graal.graph.NodeClass.NodeClassIterator; import com.oracle.graal.graph.NodeClass.Position; import com.oracle.graal.java.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.schedule.*; /**
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Mon Oct 08 17:30:11 2012 +0200 @@ -29,11 +29,11 @@ import com.oracle.graal.api.meta.JavaType.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.PhiNode.PhiType; import com.oracle.graal.nodes.VirtualState.NodeClosure; import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*;
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PostOrderBlockIterator.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PostOrderBlockIterator.java Mon Oct 08 17:30:11 2012 +0200 @@ -25,8 +25,8 @@ import java.util.*; import com.oracle.graal.graph.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; public abstract class PostOrderBlockIterator<T extends MergeableBlockState<T>> {
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/BlockIteratorClosure.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/BlockIteratorClosure.java Mon Oct 08 17:30:11 2012 +0200 @@ -24,8 +24,8 @@ import java.util.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.virtual.phases.ea.*; public abstract class BlockIteratorClosure<T extends MergeableBlockState<T>> {
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/ReentrantBlockIterator.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/ReentrantBlockIterator.java Mon Oct 08 17:30:11 2012 +0200 @@ -24,8 +24,8 @@ import java.util.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.virtual.phases.ea.*; import com.oracle.graal.virtual.phases.ea.experimental.BlockIteratorClosure.*;
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/SplitPartialEscapeAnalysisPhase.java Mon Oct 08 17:18:31 2012 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/SplitPartialEscapeAnalysisPhase.java Mon Oct 08 17:30:11 2012 +0200 @@ -29,11 +29,11 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.PhiNode.PhiType; import com.oracle.graal.nodes.VirtualState.NodeClosure; import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*;