hotspot/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.nodes/src/org/graalvm/compiler/nodes/cfg/Block.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.nodes/src/org/graalvm/compiler/nodes/cfg/Block.java Thu Feb 16 15:46:09 2017 -0800
@@ -0,0 +1,326 @@
+/*
+ * Copyright (c) 2009, 2016, 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 org.graalvm.compiler.nodes.cfg;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+
+import org.graalvm.compiler.core.common.LocationIdentity;
+import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
+import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
+import org.graalvm.compiler.core.common.cfg.Loop;
+import org.graalvm.compiler.graph.Node;
+import org.graalvm.compiler.nodes.AbstractBeginNode;
+import org.graalvm.compiler.nodes.FixedNode;
+import org.graalvm.compiler.nodes.FixedWithNextNode;
+import org.graalvm.compiler.nodes.InvokeWithExceptionNode;
+import org.graalvm.compiler.nodes.LoopBeginNode;
+import org.graalvm.compiler.nodes.LoopEndNode;
+import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
+
+public final class Block extends AbstractBlockBase<Block> {
+
+ public static final Block[] EMPTY_ARRAY = new Block[0];
+
+ protected final AbstractBeginNode beginNode;
+
+ protected FixedNode endNode;
+
+ protected double probability;
+ protected Loop<Block> loop;
+
+ protected Block postdominator;
+ protected Block distancedDominatorCache;
+ private LocationSet killLocations;
+ private LocationSet killLocationsBetweenThisAndDominator;
+
+ protected Block(AbstractBeginNode node) {
+ this.beginNode = node;
+ }
+
+ public AbstractBeginNode getBeginNode() {
+ return beginNode;
+ }
+
+ public FixedNode getEndNode() {
+ return endNode;
+ }
+
+ @Override
+ public Loop<Block> getLoop() {
+ return loop;
+ }
+
+ public void setLoop(Loop<Block> loop) {
+ this.loop = loop;
+ }
+
+ @Override
+ public int getLoopDepth() {
+ return loop == null ? 0 : loop.getDepth();
+ }
+
+ @Override
+ public boolean isLoopHeader() {
+ return getBeginNode() instanceof LoopBeginNode;
+ }
+
+ @Override
+ public boolean isLoopEnd() {
+ return getEndNode() instanceof LoopEndNode;
+ }
+
+ @Override
+ public boolean isExceptionEntry() {
+ Node predecessor = getBeginNode().predecessor();
+ return predecessor != null && predecessor instanceof InvokeWithExceptionNode && getBeginNode() == ((InvokeWithExceptionNode) predecessor).exceptionEdge();
+ }
+
+ public Block getFirstPredecessor() {
+ return getPredecessors()[0];
+ }
+
+ public Block getFirstSuccessor() {
+ return getSuccessors()[0];
+ }
+
+ public Block getEarliestPostDominated() {
+ Block b = this;
+ while (true) {
+ Block dom = b.getDominator();
+ if (dom != null && dom.getPostdominator() == b) {
+ b = dom;
+ } else {
+ break;
+ }
+ }
+ return b;
+ }
+
+ @Override
+ public Block getPostdominator() {
+ return postdominator;
+ }
+
+ private class NodeIterator implements Iterator<FixedNode> {
+
+ private FixedNode cur;
+
+ NodeIterator() {
+ cur = getBeginNode();
+ }
+
+ @Override
+ public boolean hasNext() {
+ return cur != null;
+ }
+
+ @Override
+ public FixedNode next() {
+ FixedNode result = cur;
+ if (result instanceof FixedWithNextNode) {
+ FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) result;
+ FixedNode next = fixedWithNextNode.next();
+ if (next instanceof AbstractBeginNode) {
+ next = null;
+ }
+ cur = next;
+ } else {
+ cur = null;
+ }
+ assert !(cur instanceof AbstractBeginNode);
+ 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;
+ }
+
+ @Override
+ public double probability() {
+ return probability;
+ }
+
+ public void setProbability(double probability) {
+ assert probability >= 0 && Double.isFinite(probability);
+ this.probability = probability;
+ }
+
+ @Override
+ public Block getDominator(int distance) {
+ Block result = this;
+ for (int i = 0; i < distance; ++i) {
+ result = result.getDominator();
+ }
+ return result;
+ }
+
+ public boolean canKill(LocationIdentity location) {
+ if (location.isImmutable()) {
+ return false;
+ }
+ return getKillLocations().contains(location);
+ }
+
+ public LocationSet getKillLocations() {
+ if (killLocations == null) {
+ killLocations = calcKillLocations();
+ }
+ return killLocations;
+ }
+
+ private LocationSet calcKillLocations() {
+ LocationSet result = new LocationSet();
+ for (FixedNode node : this.getNodes()) {
+ if (node instanceof MemoryCheckpoint.Single) {
+ LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
+ result.add(identity);
+ } else if (node instanceof MemoryCheckpoint.Multi) {
+ for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
+ result.add(identity);
+ }
+ }
+ if (result.isAny()) {
+ break;
+ }
+ }
+ return result;
+ }
+
+ public boolean canKillBetweenThisAndDominator(LocationIdentity location) {
+ if (location.isImmutable()) {
+ return false;
+ }
+ return this.getKillLocationsBetweenThisAndDominator().contains(location);
+ }
+
+ private LocationSet getKillLocationsBetweenThisAndDominator() {
+ if (this.killLocationsBetweenThisAndDominator == null) {
+ LocationSet dominatorResult = new LocationSet();
+ Block stopBlock = getDominator();
+ if (this.isLoopHeader()) {
+ assert stopBlock.getLoopDepth() < this.getLoopDepth();
+ dominatorResult.addAll(((HIRLoop) this.getLoop()).getKillLocations());
+ } else {
+ for (Block b : this.getPredecessors()) {
+ assert !this.isLoopHeader();
+ if (b != stopBlock) {
+ dominatorResult.addAll(b.getKillLocations());
+ if (dominatorResult.isAny()) {
+ break;
+ }
+ b.calcKillLocationsBetweenThisAndTarget(dominatorResult, stopBlock);
+ if (dominatorResult.isAny()) {
+ break;
+ }
+ }
+ }
+ }
+ this.killLocationsBetweenThisAndDominator = dominatorResult;
+ }
+ return this.killLocationsBetweenThisAndDominator;
+ }
+
+ private void calcKillLocationsBetweenThisAndTarget(LocationSet result, Block stopBlock) {
+ assert AbstractControlFlowGraph.dominates(stopBlock, this);
+ if (stopBlock == this || result.isAny()) {
+ // We reached the stop block => nothing to do.
+ return;
+ } else {
+ if (stopBlock == this.getDominator()) {
+ result.addAll(this.getKillLocationsBetweenThisAndDominator());
+ } else {
+ // Divide and conquer: Aggregate kill locations from this to the dominator and then
+ // from the dominator onwards.
+ calcKillLocationsBetweenThisAndTarget(result, this.getDominator());
+ result.addAll(this.getDominator().getKillLocations());
+ if (result.isAny()) {
+ return;
+ }
+ this.getDominator().calcKillLocationsBetweenThisAndTarget(result, stopBlock);
+ }
+ }
+ }
+
+ @Override
+ public void delete() {
+
+ // adjust successor and predecessor lists
+ Block next = getSuccessors()[0];
+ for (Block pred : getPredecessors()) {
+ Block[] predSuccs = pred.successors;
+ Block[] newPredSuccs = new Block[predSuccs.length];
+ for (int i = 0; i < predSuccs.length; ++i) {
+ if (predSuccs[i] == this) {
+ newPredSuccs[i] = next;
+ } else {
+ newPredSuccs[i] = predSuccs[i];
+ }
+ }
+ pred.setSuccessors(newPredSuccs);
+ }
+
+ ArrayList<Block> newPreds = new ArrayList<>();
+ for (int i = 0; i < next.getPredecessorCount(); i++) {
+ Block curPred = next.getPredecessors()[i];
+ if (curPred == this) {
+ for (Block b : getPredecessors()) {
+ newPreds.add(b);
+ }
+ } else {
+ newPreds.add(curPred);
+ }
+ }
+
+ next.setPredecessors(newPreds.toArray(new Block[0]));
+ }
+}