# HG changeset patch
# User Michael Van De Vanter
# Date 1399955369 25200
# Node ID 357e7202de5b24648acf0f767713ddf06a59ecc8
# Parent bb9473723904ff828b24cb20cdc15328c7494c77# Parent d556971b409ca9f5ff13900d8b7b82549fd1f17a
Merge with d556971b409ca9f5ff13900d8b7b82549fd1f17a
diff -r bb9473723904 -r 357e7202de5b .hgtags
--- a/.hgtags Mon May 12 20:17:25 2014 -0700
+++ b/.hgtags Mon May 12 21:29:29 2014 -0700
@@ -405,3 +405,4 @@
41f4cad94c581034d4c427d2aaabcc20f26342d0 hs25-b63
b124e22eb772806c13d942cc110de38da0108147 graal-0.1
483d05bf77a7c2a762aca1e06c4191bc06647176 graal-0.2
+9535eccd2a115f6c6f0b15efb508b11ff74cc0d3 graal-0.3
diff -r bb9473723904 -r 357e7202de5b CHANGELOG.md
--- a/CHANGELOG.md Mon May 12 20:17:25 2014 -0700
+++ b/CHANGELOG.md Mon May 12 21:29:29 2014 -0700
@@ -2,6 +2,16 @@
## `tip`
### Graal
+* Made initialization of Graal runtime lazy in hosted mode.
+
+### Truffle
+* `truffle.jar`: strip out build-time only dependency into a seperated JAR file (`truffle-dsl-processor.jar`)
+* ...
+
+## Version 0.3
+9-May-2014, [Repository Revision](http://hg.openjdk.java.net/graal/graal/rev/graal-0.3)
+
+### Graal
* Explicit support for oop compression/uncompression in high level graph.
* LIRGenerator refactoring.
* Explicit types for inputs (InputType enum).
@@ -9,18 +19,16 @@
* Transitioned to JDK 8 as minimum JDK level for Graal.
* Added support for stack introspection.
* New MatchRule facility to convert multiple HIR nodes into specialized LIR
-* ...
### Truffle
* The method `CallTarget#call` takes now a variable number of Object arguments.
-* Support for collecting stack traces and for accessing the current frame in slow paths.
+* Support for collecting stack traces and for accessing the current frame in slow paths (see `TruffleRuntime#getStackTrace`).
* Renamed `CallNode` to `DirectCallNode`.
* Renamed `TruffleRuntime#createCallNode` to `TruffleRuntime#createDirectCallNode`.
* Added `IndirectCallNode` for calls with a changing `CallTarget`.
* Added `TruffleRuntime#createIndirectCallNode` to create an `IndirectCallNode`.
* `DirectCallNode#inline` was renamed to `DirectCallNode#forceInlining()`.
* Removed deprecated `Node#adoptChild`.
-* ...
## Version 0.2
25-Mar-2014, [Repository Revision](http://hg.openjdk.java.net/graal/graal/rev/graal-0.2)
@@ -67,4 +75,3 @@
* Initial version of a multi-language framework on top of Graal.
* Update of the [Truffle Inlining API](http://mail.openjdk.java.net/pipermail/graal-dev/2014-January/001516.html).
-
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Mon May 12 21:29:29 2014 -0700
@@ -166,16 +166,16 @@
}
Loop loop = block.getLoop();
- if (block.isLoopEnd() && skipLoopHeader(loop.header)) {
+ if (block.isLoopEnd() && skipLoopHeader(loop.getHeader())) {
// This is the only loop end of a skipped loop header.
// Add the header immediately afterwards.
- addBlock(loop.header, order);
+ addBlock(loop.getHeader(), order);
// Make sure the loop successors of the loop header are aligned
// as they are the target
// of the backward jump.
- for (T successor : loop.header.getSuccessors()) {
+ for (T successor : loop.getHeader().getSuccessors()) {
if (successor.getLoopDepth() == block.getLoopDepth()) {
successor.setAlign(true);
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.api.collections/src/com/oracle/graal/api/collections/CollectionsProvider.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.api.collections/src/com/oracle/graal/api/collections/CollectionsProvider.java Mon May 12 21:29:29 2014 -0700
@@ -0,0 +1,56 @@
+/*
+ * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.api.collections;
+
+import java.util.*;
+
+/**
+ * A factory for creating collections.
+ */
+public interface CollectionsProvider {
+
+ /**
+ * Creates a set that uses reference-equality in place of object-equality when comparing
+ * entries.
+ */
+ Set newIdentitySet();
+
+ /**
+ * Creates a map that uses reference-equality in place of object-equality when comparing keys.
+ */
+ Map newIdentityMap();
+
+ /**
+ * Creates a map that uses reference-equality in place of object-equality when comparing keys.
+ *
+ * @param expectedMaxSize the expected maximum size of the map
+ */
+ Map newIdentityMap(int expectedMaxSize);
+
+ /**
+ * Creates a map that uses reference-equality in place of object-equality when comparing keys.
+ *
+ * @param initFrom the returned map is populated with the entries in this map
+ */
+ Map newIdentityMap(Map initFrom);
+}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.api.collections/src/com/oracle/graal/api/collections/DefaultCollectionsProvider.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.api.collections/src/com/oracle/graal/api/collections/DefaultCollectionsProvider.java Mon May 12 21:29:29 2014 -0700
@@ -0,0 +1,48 @@
+/*
+ * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.api.collections;
+
+import java.util.*;
+
+/**
+ * A default implementation of {@link CollectionsProvider} that creates standard JDK collection
+ * class objects.
+ */
+public class DefaultCollectionsProvider implements CollectionsProvider {
+
+ public Set newIdentitySet() {
+ return Collections.newSetFromMap(newIdentityMap());
+ }
+
+ public Map newIdentityMap() {
+ return new IdentityHashMap<>();
+ }
+
+ public Map newIdentityMap(int expectedMaxSize) {
+ return new IdentityHashMap<>(expectedMaxSize);
+ }
+
+ public Map newIdentityMap(Map initFrom) {
+ return new IdentityHashMap<>(initFrom);
+ }
+}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.api.runtime/src/com/oracle/graal/api/runtime/Graal.java
--- a/graal/com.oracle.graal.api.runtime/src/com/oracle/graal/api/runtime/Graal.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.api.runtime/src/com/oracle/graal/api/runtime/Graal.java Mon May 12 21:29:29 2014 -0700
@@ -28,7 +28,7 @@
public class Graal {
- private static GraalRuntime runtime;
+ private static final GraalRuntime runtime;
private static native GraalRuntime initializeRuntime();
@@ -47,12 +47,13 @@
}
static {
+ GraalRuntime rt;
try {
- runtime = initializeRuntime();
+ rt = initializeRuntime();
} catch (UnsatisfiedLinkError e) {
- runtime = new InvalidGraalRuntime();
+ rt = new InvalidGraalRuntime();
}
-
+ runtime = rt;
Reflection.registerFieldsToFilter(Graal.class, "runtime");
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java
--- a/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java Mon May 12 21:29:29 2014 -0700
@@ -35,6 +35,7 @@
import com.oracle.graal.compiler.common.*;
import com.oracle.graal.compiler.common.calc.*;
import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.compiler.common.type.*;
import com.oracle.graal.compiler.gen.*;
import com.oracle.graal.compiler.target.*;
import com.oracle.graal.debug.*;
@@ -92,8 +93,14 @@
try (Indent indent = Debug.logAndIndent("build graph for %s", method)) {
- // compute the block map, setup exception handlers and get the entrypoint(s)
- BciBlockMapping blockMap = BciBlockMapping.create(method);
+ BciBlockMapping blockMap;
+ try (Scope ds = Debug.scope("BciBlockMapping")) {
+ // compute the block map, setup exception handlers and get the entrypoint(s)
+ blockMap = BciBlockMapping.create(method);
+ } catch (Throwable e) {
+ throw Debug.handle(e);
+ }
+
loopHeaders = blockMap.loopHeaders;
liveness = blockMap.liveness;
blockVisited = new BciBlockBitMap(blockMap);
@@ -120,7 +127,7 @@
// add loops ? how do we add looks when we haven't parsed the bytecode?
// create the control flow graph
- BaselineControlFlowGraph cfg = new BaselineControlFlowGraph(blockMap);
+ BaselineControlFlowGraph cfg = BaselineControlFlowGraph.compute(blockMap);
// create the LIR
List extends AbstractBlock>> linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blockMap.blocks.size(), blockMap.startBlock);
@@ -471,14 +478,21 @@
@Override
protected Value genLoadField(Value receiver, ResolvedJavaField field) {
+ if (field.isStatic()) {
+ Value classRef = lirBuilder.getClassConstant(field.getDeclaringClass());
+ long displacement = lirBuilder.getFieldOffset(field);
+ Value address = gen.emitAddress(classRef, displacement, Value.ILLEGAL, 0);
+ PlatformKind readKind = gen.getPlatformKind(StampFactory.forKind(field.getKind()));
+ LIRFrameState state = createFrameState(frameState);
+ return gen.emitLoad(readKind, address, state);
+ }
// TODO Auto-generated method stub
throw GraalInternalError.unimplemented("Auto-generated method stub");
}
@Override
protected void emitNullCheck(Value receiver) {
- // TODO Auto-generated method stub
- throw GraalInternalError.unimplemented("Auto-generated method stub");
+ gen.emitNullCheck(receiver, createFrameState(frameState));
}
@Override
@@ -488,9 +502,38 @@
}
@Override
- protected Value genArrayLength(Value x) {
- // TODO Auto-generated method stub
- throw GraalInternalError.unimplemented("Auto-generated method stub");
+ protected Value genArrayLength(Value array) {
+ emitNullCheck(array);
+ long displacement = lirBuilder.getArrayLengthOffset();
+ Value address = gen.emitAddress(array, displacement, Value.ILLEGAL, 0);
+ PlatformKind readKind = gen.getPlatformKind(StampFactory.forKind(Kind.Int));
+ LIRFrameState state = createFrameState(frameState);
+ return gen.emitLoad(readKind, address, state);
+ }
+
+ private LIRFrameState createFrameState(BaselineFrameStateBuilder state) {
+ LabelRef exceptionEdge = null;
+ BytecodeFrame caller = null;
+ boolean duringCall = false;
+ int numLocals = state.localsSize();
+ int numStack = state.stackSize();
+ int numLocks = state.lockDepth();
+ Value[] values = new Value[numLocals + numStack + numLocks];
+
+ for (int i = 0; i < numLocals; i++) {
+ values[i] = state.localAt(i);
+ }
+
+ for (int i = 0; i < numStack; i++) {
+ values[numLocals + i] = state.stackAt(i);
+ }
+
+ for (int i = 0; i < numStack; i++) {
+ values[numLocals + numStack + i] = state.lockAt(i);
+ }
+
+ BytecodeFrame frame = new BytecodeFrame(caller, method, bci(), state.rethrowException(), duringCall, values, numLocals, numStack, numLocks);
+ return new LIRFrameState(frame, null, exceptionEdge);
}
@Override
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineControlFlowGraph.java
--- a/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineControlFlowGraph.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineControlFlowGraph.java Mon May 12 21:29:29 2014 -0700
@@ -24,24 +24,33 @@
import java.util.*;
-import com.oracle.graal.compiler.common.*;
import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.debug.Debug.Scope;
import com.oracle.graal.java.*;
import com.oracle.graal.java.BciBlockMapping.BciBlock;
public class BaselineControlFlowGraph implements AbstractControlFlowGraph {
- private BciBlock[] blocks;
+ private List blocks;
private Collection> loops;
- private BitSet visited;
- public BaselineControlFlowGraph(BciBlockMapping blockMap) {
- blocks = blockMap.blocks.toArray(new BciBlock[0]);
- loops = new ArrayList<>();
- computeLoopInformation();
+ public static BaselineControlFlowGraph compute(BciBlockMapping blockMap) {
+ try (Scope ds = Debug.scope("BaselineCFG", blockMap)) {
+ BaselineControlFlowGraph cfg = new BaselineControlFlowGraph(blockMap);
+ cfg.computeLoopInformation(blockMap);
+ return cfg;
+ } catch (Throwable e) {
+ throw Debug.handle(e);
+ }
}
- public BciBlock[] getBlocks() {
+ private BaselineControlFlowGraph(BciBlockMapping blockMap) {
+ blocks = blockMap.blocks;
+ loops = new ArrayList<>();
+ }
+
+ public List getBlocks() {
return blocks;
}
@@ -50,50 +59,53 @@
}
public BciBlock getStartBlock() {
- if (blocks.length > 0) {
- return blocks[0];
+ if (!blocks.isEmpty()) {
+ return blocks.get(0);
}
return null;
}
- private void computeLoopInformation() {
- visited = new BitSet(blocks.length);
- Deque stack = new ArrayDeque<>();
- for (int i = blocks.length - 1; i >= 0; i--) {
- BciBlock block = blocks[i];
- calcLoop(block, stack);
+ private void computeLoopInformation(BciBlockMapping blockMap) {
+ try (Indent indent = Debug.logAndIndent("computeLoopInformation")) {
+ for (BciBlock block : blocks) {
+ calcLoop(block, blockMap);
+ Debug.log("Block: %s, Loop: %s", block, block.getLoop());
+ }
}
}
- private void calcLoop(BciBlock block, Deque stack) {
- if (visited.get(block.getId())) {
- return;
+ private Loop getLoop(int index, BciBlockMapping blockMap) {
+ BciBlock header = blockMap.getLoopHeader(index);
+ assert header.getLoopDepth() > 0;
+ Loop loop = header.getLoop();
+
+ if (loop == null) {
+ Loop parent = null;
+
+ if (header.getLoopDepth() > 1) {
+ // Recursively create out loops.
+ Iterator i = header.loopIdIterable().iterator();
+ assert i.hasNext() : "BciBlock.loopIdIterable() must return exactly BciBlock.getLoopDepth() elements!";
+ int outerLoopId = i.next();
+ assert index == outerLoopId : "The first loopId must be the id of the loop that is started by this header!";
+ assert i.hasNext() : "BciBlock.loopIdIterable() must return exactly BciBlock.getLoopDepth() elements!";
+ outerLoopId = i.next();
+ parent = getLoop(outerLoopId, blockMap);
+ }
+
+ loop = new BaselineLoop(parent, index, header);
+ loops.add(loop);
+ header.setLoop(loop);
}
- visited.set(block.getId());
- if (block.isLoopEnd()) {
- BciBlock loopHeader = getLoopHeader(block);
- BaselineLoop l = new BaselineLoop(stack.peek(), loops.size(), loopHeader);
- loops.add(l);
- stack.push(l);
- }
- block.loop = stack.peek();
- if (block.isLoopHeader()) {
- assert block.loop.header.equals(block);
- stack.pop();
- }
- for (BciBlock pred : block.getPredecessors()) {
- calcLoop(pred, stack);
+ return loop;
+ }
+
+ private void calcLoop(BciBlock block, BciBlockMapping blockMap) {
+ int loopId = block.getLoopId();
+ if (loopId != -1) {
+ block.setLoop(getLoop(loopId, blockMap));
+
}
}
- private static BciBlock getLoopHeader(BciBlock block) {
- assert block.isLoopEnd();
- for (BciBlock sux : block.getSuccessors()) {
- if (sux.isLoopHeader() && sux.getId() <= block.getId() && block.loops == sux.loops) {
- return sux;
- }
- }
- throw GraalInternalError.shouldNotReachHere("No loop header found for " + block);
- }
-
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64LIRGenerator.java
--- a/graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64LIRGenerator.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64LIRGenerator.java Mon May 12 21:29:29 2014 -0700
@@ -601,7 +601,7 @@
}
}
- protected Value emitBinaryMemory(AMD64Arithmetic op, Kind kind, AllocatableValue a, AMD64AddressValue location, LIRFrameState state) {
+ public Value emitBinaryMemory(AMD64Arithmetic op, Kind kind, AllocatableValue a, AMD64AddressValue location, LIRFrameState state) {
Variable result = newVariable(a.getKind());
append(new BinaryMemory(op, kind, result, a, location, state));
return result;
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64NodeLIRBuilder.java
--- a/graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64NodeLIRBuilder.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64NodeLIRBuilder.java Mon May 12 21:29:29 2014 -0700
@@ -56,12 +56,6 @@
}
@Override
- public void emitNullCheck(ValueNode v, DeoptimizingNode deopt) {
- assert v.getKind() == Kind.Object : v + " - " + v.stamp() + " @ " + deopt;
- append(new AMD64Move.NullCheckOp(gen.load(operand(v)), state(deopt)));
- }
-
- @Override
protected boolean peephole(ValueNode valueNode) {
if ((valueNode instanceof IntegerDivNode) || (valueNode instanceof IntegerRemNode)) {
FixedBinaryNode divRem = (FixedBinaryNode) valueNode;
@@ -316,7 +310,7 @@
throw GraalInternalError.shouldNotReachHere();
}
- private AMD64Arithmetic getOp(ValueNode operation, Access access) {
+ protected AMD64Arithmetic getOp(ValueNode operation, Access access) {
Kind memoryKind = getMemoryKind(access);
if (operation.getClass() == IntegerAddNode.class) {
switch (memoryKind) {
@@ -455,7 +449,7 @@
return null;
}
- @MatchRule("(Write Narrow=narrow value)")
+ @MatchRule("(Write Narrow=narrow location value)")
public ComplexMatchResult writeNarrow(WriteNode root, NarrowNode narrow) {
return builder -> {
PlatformKind writeKind = getLIRGeneratorTool().getPlatformKind(root.value().stamp());
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlock.java
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlock.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlock.java Mon May 12 21:29:29 2014 -0700
@@ -30,6 +30,8 @@
Loop getLoop();
+ void setLoop(Loop loop);
+
int getLoopDepth();
boolean isLoopHeader();
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java Mon May 12 21:29:29 2014 -0700
@@ -29,7 +29,7 @@
static final int BLOCK_ID_INITIAL = -1;
static final int BLOCK_ID_VISITED = -2;
- T[] getBlocks();
+ List getBlocks();
Collection> getLoops();
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/BlockMap.java
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/BlockMap.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/BlockMap.java Mon May 12 21:29:29 2014 -0700
@@ -28,7 +28,7 @@
@SuppressWarnings("unchecked")
public BlockMap(AbstractControlFlowGraph> cfg) {
- data = (T[]) new Object[cfg.getBlocks().length];
+ data = (T[]) new Object[cfg.getBlocks().size()];
}
public T get(AbstractBlock> block) {
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/Loop.java
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/Loop.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/Loop.java Mon May 12 21:29:29 2014 -0700
@@ -27,20 +27,20 @@
public abstract class Loop> {
- public final Loop parent;
- public final List> children;
+ private final Loop parent;
+ private final List> children;
- public final int depth;
- public final int index;
- public final T header;
- public final List blocks;
- public final List exits;
+ private final int depth;
+ private final int index;
+ private final T header;
+ private final List blocks;
+ private final List exits;
protected Loop(Loop parent, int index, T header) {
this.parent = parent;
if (parent != null) {
- this.depth = parent.depth + 1;
- parent.children.add(this);
+ this.depth = parent.getDepth() + 1;
+ parent.getChildren().add(this);
} else {
this.depth = 1;
}
@@ -55,6 +55,34 @@
@Override
public String toString() {
- return "loop " + index + " depth " + depth + (parent != null ? " outer " + parent.index : "");
+ return "loop " + index + " depth " + getDepth() + (parent != null ? " outer " + parent.index : "");
+ }
+
+ public Loop getParent() {
+ return parent;
+ }
+
+ public List> getChildren() {
+ return children;
+ }
+
+ public int getDepth() {
+ return depth;
+ }
+
+ public int getIndex() {
+ return index;
+ }
+
+ public T getHeader() {
+ return header;
+ }
+
+ public List getBlocks() {
+ return blocks;
+ }
+
+ public List getExits() {
+ return exits;
}
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/type/IntegerStamp.java
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/type/IntegerStamp.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/type/IntegerStamp.java Mon May 12 21:29:29 2014 -0700
@@ -183,7 +183,7 @@
private Stamp createStamp(IntegerStamp other, long newUpperBound, long newLowerBound, long newDownMask, long newUpMask) {
assert getBits() == other.getBits();
- if (newLowerBound > newUpperBound || (newDownMask & (~newUpMask)) != 0) {
+ if (newLowerBound > newUpperBound || (newDownMask & (~newUpMask)) != 0 || (newUpMask == 0 && (newLowerBound > 0 || newUpperBound < 0))) {
return illegal();
} else if (newLowerBound == lowerBound && newUpperBound == upperBound && newDownMask == downMask && newUpMask == upMask) {
return this;
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.hsail/src/com/oracle/graal/compiler/hsail/HSAILNodeLIRBuilder.java
--- a/graal/com.oracle.graal.compiler.hsail/src/com/oracle/graal/compiler/hsail/HSAILNodeLIRBuilder.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.hsail/src/com/oracle/graal/compiler/hsail/HSAILNodeLIRBuilder.java Mon May 12 21:29:29 2014 -0700
@@ -25,11 +25,9 @@
import com.oracle.graal.api.meta.*;
import com.oracle.graal.compiler.common.*;
-import com.oracle.graal.compiler.common.type.*;
import com.oracle.graal.compiler.gen.*;
import com.oracle.graal.lir.*;
import com.oracle.graal.lir.gen.*;
-import com.oracle.graal.lir.hsail.*;
import com.oracle.graal.nodes.*;
/**
@@ -63,14 +61,6 @@
}
@Override
- public void emitNullCheck(ValueNode v, DeoptimizingNode deopting) {
- assert v.stamp() instanceof ObjectStamp;
- Variable obj = newVariable(Kind.Object);
- gen.emitMove(obj, operand(v));
- append(new HSAILMove.NullCheckOp(obj, state(deopting)));
- }
-
- @Override
public void visitInfopointNode(InfopointNode i) {
// TODO Auto-generated method stub
throw GraalInternalError.unimplemented();
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.ptx/src/com/oracle/graal/compiler/ptx/PTXLIRGenerator.java
--- a/graal/com.oracle.graal.compiler.ptx/src/com/oracle/graal/compiler/ptx/PTXLIRGenerator.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.ptx/src/com/oracle/graal/compiler/ptx/PTXLIRGenerator.java Mon May 12 21:29:29 2014 -0700
@@ -894,4 +894,9 @@
throw GraalInternalError.unimplemented();
}
+ public void emitNullCheck(Value address, LIRFrameState state) {
+ assert address.getKind() == Kind.Object : address + " - " + address.getKind() + " not an object!";
+ append(new PTXMove.NullCheckOp(load(address), state));
+ }
+
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.ptx/src/com/oracle/graal/compiler/ptx/PTXNodeLIRBuilder.java
--- a/graal/com.oracle.graal.compiler.ptx/src/com/oracle/graal/compiler/ptx/PTXNodeLIRBuilder.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.ptx/src/com/oracle/graal/compiler/ptx/PTXNodeLIRBuilder.java Mon May 12 21:29:29 2014 -0700
@@ -40,11 +40,6 @@
*/
public class PTXNodeLIRBuilder extends NodeLIRBuilder {
- // Number of the predicate register that can be used when needed.
- // This value will be recorded and incremented in the LIR instruction
- // that sets a predicate register. (e.g., CompareOp)
- private int nextPredRegNum;
-
public static final ForeignCallDescriptor ARITHMETIC_FREM = new ForeignCallDescriptor("arithmeticFrem", float.class, float.class, float.class);
public static final ForeignCallDescriptor ARITHMETIC_DREM = new ForeignCallDescriptor("arithmeticDrem", double.class, double.class, double.class);
@@ -60,10 +55,6 @@
super(graph, lirGen);
}
- public int getNextPredRegNumber() {
- return nextPredRegNum;
- }
-
@Override
public void emitPrologue(StructuredGraph graph) {
// Need to emit .param directives based on incoming arguments and return value
@@ -134,12 +125,6 @@
}
@Override
- public void emitNullCheck(ValueNode v, DeoptimizingNode deopting) {
- assert v.getKind() == Kind.Object;
- append(new PTXMove.NullCheckOp(gen.load(operand(v)), state(deopting)));
- }
-
- @Override
public void visitInfopointNode(InfopointNode i) {
throw GraalInternalError.unimplemented("PTXLIRGenerator.visitInfopointNode()");
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.sparc/src/com/oracle/graal/compiler/sparc/SPARCNodeLIRBuilder.java
--- a/graal/com.oracle.graal.compiler.sparc/src/com/oracle/graal/compiler/sparc/SPARCNodeLIRBuilder.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.sparc/src/com/oracle/graal/compiler/sparc/SPARCNodeLIRBuilder.java Mon May 12 21:29:29 2014 -0700
@@ -29,7 +29,6 @@
import com.oracle.graal.compiler.gen.*;
import com.oracle.graal.lir.gen.*;
import com.oracle.graal.lir.sparc.*;
-import com.oracle.graal.lir.sparc.SPARCMove.NullCheckOp;
import com.oracle.graal.nodes.*;
/**
@@ -59,12 +58,6 @@
}
@Override
- public void emitNullCheck(ValueNode v, DeoptimizingNode deopting) {
- assert v.getKind() == Kind.Object;
- append(new NullCheckOp(gen.load(operand(v)), state(deopting)));
- }
-
- @Override
public void visitInfopointNode(InfopointNode i) {
// TODO Auto-generated method stub
throw GraalInternalError.unimplemented();
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/FlowSenReduTest.java
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/FlowSenReduTest.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/FlowSenReduTest.java Mon May 12 21:29:29 2014 -0700
@@ -384,7 +384,7 @@
public StructuredGraph visualize(StructuredGraph graph, String title) {
DebugConfig debugConfig = DebugScope.getConfig();
- DebugConfig fixedConfig = Debug.fixedConfig(false, true, false, false, debugConfig.dumpHandlers(), debugConfig.output());
+ DebugConfig fixedConfig = Debug.fixedConfig(false, true, false, false, false, debugConfig.dumpHandlers(), debugConfig.output());
try (DebugConfigScope s = Debug.setConfig(fixedConfig)) {
Debug.dump(graph, title);
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java Mon May 12 21:29:29 2014 -0700
@@ -164,7 +164,7 @@
@Test
public void testLoop1() {
SchedulePhase schedule = getFinalSchedule("testLoop1Snippet", TestMode.WITHOUT_FRAMESTATES);
- assertEquals(6, schedule.getCFG().getBlocks().length);
+ assertEquals(6, schedule.getCFG().getBlocks().size());
assertReadWithinStartBlock(schedule, true);
assertReadWithinAllReturnBlocks(schedule, false);
}
@@ -189,7 +189,7 @@
@Test
public void testLoop2() {
SchedulePhase schedule = getFinalSchedule("testLoop2Snippet", TestMode.WITHOUT_FRAMESTATES);
- assertEquals(6, schedule.getCFG().getBlocks().length);
+ assertEquals(6, schedule.getCFG().getBlocks().size());
assertReadWithinStartBlock(schedule, false);
assertReadWithinAllReturnBlocks(schedule, true);
}
@@ -211,7 +211,7 @@
@Test
public void testLoop3() {
SchedulePhase schedule = getFinalSchedule("testLoop3Snippet", TestMode.WITHOUT_FRAMESTATES);
- assertEquals(6, schedule.getCFG().getBlocks().length);
+ assertEquals(6, schedule.getCFG().getBlocks().size());
assertReadWithinStartBlock(schedule, true);
assertReadWithinAllReturnBlocks(schedule, false);
}
@@ -247,7 +247,7 @@
@Test
public void testLoop5() {
SchedulePhase schedule = getFinalSchedule("testLoop5Snippet", TestMode.WITHOUT_FRAMESTATES);
- assertEquals(10, schedule.getCFG().getBlocks().length);
+ assertEquals(10, schedule.getCFG().getBlocks().size());
assertReadWithinStartBlock(schedule, false);
assertReadWithinAllReturnBlocks(schedule, false);
}
@@ -285,7 +285,7 @@
@Test
public void testIfRead1() {
SchedulePhase schedule = getFinalSchedule("testIfRead1Snippet", TestMode.WITHOUT_FRAMESTATES);
- assertEquals(3, schedule.getCFG().getBlocks().length);
+ assertEquals(3, schedule.getCFG().getBlocks().size());
assertReadWithinStartBlock(schedule, true);
assertReadAndWriteInSameBlock(schedule, false);
}
@@ -306,7 +306,7 @@
@Test
public void testIfRead2() {
SchedulePhase schedule = getFinalSchedule("testIfRead2Snippet", TestMode.WITHOUT_FRAMESTATES);
- assertEquals(3, schedule.getCFG().getBlocks().length);
+ assertEquals(3, schedule.getCFG().getBlocks().size());
assertEquals(1, schedule.getCFG().graph.getNodes().filter(FloatingReadNode.class).count());
assertReadWithinStartBlock(schedule, false);
assertReadWithinAllReturnBlocks(schedule, false);
@@ -328,7 +328,7 @@
@Test
public void testIfRead3() {
SchedulePhase schedule = getFinalSchedule("testIfRead3Snippet", TestMode.WITHOUT_FRAMESTATES);
- assertEquals(4, schedule.getCFG().getBlocks().length);
+ assertEquals(4, schedule.getCFG().getBlocks().size());
assertReadWithinStartBlock(schedule, false);
assertReadWithinAllReturnBlocks(schedule, true);
}
@@ -349,7 +349,7 @@
@Test
public void testIfRead4() {
SchedulePhase schedule = getFinalSchedule("testIfRead4Snippet", TestMode.WITHOUT_FRAMESTATES);
- assertEquals(3, schedule.getCFG().getBlocks().length);
+ assertEquals(3, schedule.getCFG().getBlocks().size());
assertReadWithinStartBlock(schedule, false);
assertReadWithinAllReturnBlocks(schedule, false);
assertReadAndWriteInSameBlock(schedule, true);
@@ -368,7 +368,7 @@
@Test
public void testIfRead5() {
SchedulePhase schedule = getFinalSchedule("testIfRead5Snippet", TestMode.WITHOUT_FRAMESTATES);
- assertEquals(4, schedule.getCFG().getBlocks().length);
+ assertEquals(4, schedule.getCFG().getBlocks().size());
assertReadWithinStartBlock(schedule, false);
assertReadWithinAllReturnBlocks(schedule, true);
assertReadAndWriteInSameBlock(schedule, false);
@@ -397,7 +397,7 @@
StructuredGraph graph = schedule.getCFG().graph;
NodeIterable writeNodes = graph.getNodes().filter(WriteNode.class);
- assertEquals(1, schedule.getCFG().getBlocks().length);
+ assertEquals(1, schedule.getCFG().getBlocks().size());
assertEquals(8, writeNodes.count());
assertEquals(1, graph.getNodes().filter(FloatingReadNode.class).count());
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/NestedLoopTest.java
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/NestedLoopTest.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/NestedLoopTest.java Mon May 12 21:29:29 2014 -0700
@@ -163,20 +163,20 @@
Assert.assertTrue(containsDirect(innerMostLoop, d, cfg));
Assert.assertTrue(contains(rootLoop, d, cfg));
Assert.assertTrue(contains(nestedLoop, d, cfg));
- Assert.assertEquals(rootExits, rootLoop.exits.size());
- Assert.assertEquals(nestedExits, nestedLoop.exits.size());
- Assert.assertEquals(innerExits, innerMostLoop.exits.size());
+ Assert.assertEquals(rootExits, rootLoop.getExits().size());
+ Assert.assertEquals(nestedExits, nestedLoop.getExits().size());
+ Assert.assertEquals(innerExits, innerMostLoop.getExits().size());
Debug.dump(graph, "Graph");
}
private static boolean contains(Loop loop, Invoke node, ControlFlowGraph cfg) {
Block block = cfg.blockFor((Node) node);
Assert.assertNotNull(block);
- return loop.blocks.contains(block);
+ return loop.getBlocks().contains(block);
}
private static boolean containsDirect(Loop loop, Invoke node, ControlFlowGraph cfg) {
- for (Loop child : loop.children) {
+ for (Loop child : loop.getChildren()) {
if (contains(child, node, cfg)) {
return false;
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SimpleCFGTest.java
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SimpleCFGTest.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SimpleCFGTest.java Mon May 12 21:29:29 2014 -0700
@@ -22,6 +22,10 @@
*/
package com.oracle.graal.compiler.test;
+import static org.junit.Assert.assertTrue;
+
+import java.util.*;
+
import org.junit.*;
import com.oracle.graal.debug.*;
@@ -59,37 +63,45 @@
ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true);
- Block[] blocks = cfg.getBlocks();
+ List blocks = cfg.getBlocks();
// check number of blocks
- assertEquals(4, blocks.length);
+ assertEquals(4, blocks.size());
// check block - node assignment
- assertEquals(blocks[0], cfg.blockFor(graph.start()));
- assertEquals(blocks[0], cfg.blockFor(ifNode));
- assertEquals(blocks[1], cfg.blockFor(trueBegin));
- assertEquals(blocks[1], cfg.blockFor(trueEnd));
- assertEquals(blocks[2], cfg.blockFor(falseBegin));
- assertEquals(blocks[2], cfg.blockFor(falseEnd));
- assertEquals(blocks[3], cfg.blockFor(merge));
- assertEquals(blocks[3], cfg.blockFor(returnNode));
+ assertEquals(blocks.get(0), cfg.blockFor(graph.start()));
+ assertEquals(blocks.get(0), cfg.blockFor(ifNode));
+ assertEquals(blocks.get(1), cfg.blockFor(trueBegin));
+ assertEquals(blocks.get(1), cfg.blockFor(trueEnd));
+ assertEquals(blocks.get(2), cfg.blockFor(falseBegin));
+ assertEquals(blocks.get(2), cfg.blockFor(falseEnd));
+ assertEquals(blocks.get(3), cfg.blockFor(merge));
+ assertEquals(blocks.get(3), cfg.blockFor(returnNode));
+
+ // check postOrder
+ Iterator it = cfg.postOrder().iterator();
+ for (int i = blocks.size() - 1; i >= 0; i--) {
+ assertTrue(it.hasNext());
+ Block b = it.next();
+ assertEquals(blocks.get(i), b);
+ }
// check dominators
- assertDominator(blocks[0], null);
- assertDominator(blocks[1], blocks[0]);
- assertDominator(blocks[2], blocks[0]);
- assertDominator(blocks[3], blocks[0]);
+ assertDominator(blocks.get(0), null);
+ assertDominator(blocks.get(1), blocks.get(0));
+ assertDominator(blocks.get(2), blocks.get(0));
+ assertDominator(blocks.get(3), blocks.get(0));
// check dominated
- assertDominatedSize(blocks[0], 3);
- assertDominatedSize(blocks[1], 0);
- assertDominatedSize(blocks[2], 0);
- assertDominatedSize(blocks[3], 0);
+ assertDominatedSize(blocks.get(0), 3);
+ assertDominatedSize(blocks.get(1), 0);
+ assertDominatedSize(blocks.get(2), 0);
+ assertDominatedSize(blocks.get(3), 0);
// check postdominators
- assertPostdominator(blocks[0], blocks[3]);
- assertPostdominator(blocks[1], blocks[3]);
- assertPostdominator(blocks[2], blocks[3]);
- assertPostdominator(blocks[3], null);
+ assertPostdominator(blocks.get(0), blocks.get(3));
+ assertPostdominator(blocks.get(1), blocks.get(3));
+ assertPostdominator(blocks.get(2), blocks.get(3));
+ assertPostdominator(blocks.get(3), null);
}
public static void assertDominator(Block block, Block expectedDominator) {
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/TypeSystemTest.java
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/TypeSystemTest.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/TypeSystemTest.java Mon May 12 21:29:29 2014 -0700
@@ -25,6 +25,7 @@
import java.io.*;
import com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase;
+
import org.junit.*;
import com.oracle.graal.api.code.*;
@@ -181,6 +182,19 @@
return ((InputStream) o).available();
}
+ @Test
+ public void test7() {
+ test("test7Snippet", "referenceSnippet7");
+ }
+
+ public static int test7Snippet(int x) {
+ return ((x & 0xff) << 10) == ((x & 0x1f) + 1) ? 0 : x;
+ }
+
+ public static int referenceSnippet7(int x) {
+ return x;
+ }
+
private void test(String snippet, String referenceSnippet) {
StructuredGraph graph = parse(snippet);
Debug.dump(graph, "Graph");
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon May 12 21:29:29 2014 -0700
@@ -218,7 +218,7 @@
}
public static LIRGenerationResult emitLIR(Backend backend, TargetDescription target, SchedulePhase schedule, StructuredGraph graph, Object stub, CallingConvention cc, RegisterConfig registerConfig) {
- Block[] blocks = schedule.getCFG().getBlocks();
+ List blocks = schedule.getCFG().getBlocks();
Block startBlock = schedule.getCFG().getStartBlock();
assert startBlock != null;
assert startBlock.getPredecessorCount() == 0;
@@ -228,8 +228,8 @@
List linearScanOrder = null;
try (Scope ds = Debug.scope("MidEnd")) {
try (Scope s = Debug.scope("ComputeLinearScanOrder")) {
- codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blocks.length, startBlock);
- linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blocks.length, startBlock);
+ codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blocks.size(), startBlock);
+ linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blocks.size(), startBlock);
lir = new LIR(schedule.getCFG(), linearScanOrder, codeEmittingOrder);
Debug.dump(lir, "After linear scan order");
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalDebugConfig.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalDebugConfig.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalDebugConfig.java Mon May 12 21:29:29 2014 -0700
@@ -42,6 +42,8 @@
public static final OptionValue Dump = new OptionValue<>(null);
@Option(help = "Pattern for scope(s) to in which metering is enabled (see DebugFilter and Debug.metric)")
public static final OptionValue Meter = new OptionValue<>(null);
+ @Option(help = "Pattern for scope(s) to in which memory use tracking is enabled (see DebugFilter and Debug.metric)")
+ public static final OptionValue TrackMemUse = new OptionValue<>(null);
@Option(help = "Pattern for scope(s) to in which timing is enabled (see DebugFilter and Debug.timer)")
public static final OptionValue Time = new OptionValue<>(null);
@Option(help = "Pattern for scope(s) to in which logging is enabled (see DebugFilter and Debug.log)")
@@ -79,11 +81,12 @@
}
public static boolean areMetricsOrTimersEnabled() {
- return Meter.getValue() != null || Time.getValue() != null;
+ return Meter.getValue() != null || Time.getValue() != null || TrackMemUse.getValue() != null;
}
private final DebugFilter logFilter;
private final DebugFilter meterFilter;
+ private final DebugFilter trackMemUseFilter;
private final DebugFilter timerFilter;
private final DebugFilter dumpFilter;
private final MethodFilter[] methodFilter;
@@ -91,9 +94,11 @@
private final PrintStream output;
private final Set
*
*/
-public abstract class BaseReduction extends PostOrderNodeIterator {
+public abstract class BaseReduction extends SinglePassNodeIterator {
- protected static final DebugMetric metricCheckCastRemoved = Debug.metric("CheckCastRemoved");
- protected static final DebugMetric metricGuardingPiNodeRemoved = Debug.metric("GuardingPiNodeRemoved");
- protected static final DebugMetric metricFixedGuardNodeRemoved = Debug.metric("FixedGuardNodeRemoved");
- protected static final DebugMetric metricMethodResolved = Debug.metric("MethodResolved");
+ protected static final DebugMetric metricCheckCastRemoved = Debug.metric("FSR-CheckCastRemoved");
+ protected static final DebugMetric metricGuardingPiNodeRemoved = Debug.metric("FSR-GuardingPiNodeRemoved");
+ protected static final DebugMetric metricFixedGuardNodeRemoved = Debug.metric("FSR-FixedGuardNodeRemoved");
+ protected static final DebugMetric metricMethodResolved = Debug.metric("FSR-MethodResolved");
+ protected static final DebugMetric metricUnconditionalDeoptInserted = Debug.metric("FSR-UnconditionalDeoptInserted");
/**
*
@@ -95,6 +96,7 @@
* a bug in FlowSensitiveReduction (the code was reachable, after all).
*/
public void doRewrite(LogicNode falseConstant) {
+ metricUnconditionalDeoptInserted.increment();
StructuredGraph graph = fixed.graph();
// have to insert a FixedNode other than a ControlSinkNode
FixedGuardNode buckStopsHere = graph.add(new FixedGuardNode(falseConstant, deoptReason, DeoptimizationAction.None));
@@ -193,7 +195,7 @@
protected final PostponedDeopts postponedDeopts = new PostponedDeopts();
- protected BaseReduction(FixedNode start, State initialState, PhaseContext context) {
+ protected BaseReduction(StartNode start, State initialState, PhaseContext context) {
super(start, initialState);
graph = start.graph();
trueConstant = LogicConstantNode.tautology(graph);
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CheckCastReduction.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CheckCastReduction.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CheckCastReduction.java Mon May 12 21:29:29 2014 -0700
@@ -50,7 +50,7 @@
*/
public abstract class CheckCastReduction extends GuardingPiReduction {
- public CheckCastReduction(FixedNode start, State initialState, PhaseContext context) {
+ public CheckCastReduction(StartNode start, State initialState, PhaseContext context) {
super(start, initialState, context);
}
@@ -122,7 +122,7 @@
assert !StampTool.isObjectAlwaysNull(subject) : "Null as per stamp subjects should have been handled above";
// --------- checkCast deemed unsatisfiable by subject-stamp alone ---------
- if (state.knownNotToConform(subject, toType)) {
+ if (state.knownNotToPassCheckCast(subject, toType)) {
postponedDeopts.addDeoptBefore(checkCast, checkCast.isForStoreCheck() ? ArrayStoreException : ClassCastException);
state.impossiblePath();
// let FixedGuardNode(false).simplify() prune the dead-code control-path
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/EquationalReasoner.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/EquationalReasoner.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/EquationalReasoner.java Mon May 12 21:29:29 2014 -0700
@@ -22,29 +22,22 @@
*/
package com.oracle.graal.phases.common.cfs;
-import com.oracle.graal.api.meta.ResolvedJavaType;
-import com.oracle.graal.debug.Debug;
-import com.oracle.graal.debug.DebugMetric;
-import com.oracle.graal.graph.Node;
-import com.oracle.graal.graph.NodeBitMap;
-import com.oracle.graal.graph.spi.CanonicalizerTool;
+import static com.oracle.graal.graph.util.CollectionsAccess.*;
+
+import java.util.*;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.compiler.common.type.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.graph.*;
+import com.oracle.graal.graph.spi.*;
import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.calc.FloatingNode;
-import com.oracle.graal.nodes.calc.IsNullNode;
-import com.oracle.graal.nodes.calc.ObjectEqualsNode;
-import com.oracle.graal.nodes.extended.GuardedNode;
-import com.oracle.graal.nodes.extended.GuardingNode;
-import com.oracle.graal.nodes.java.CheckCastNode;
-import com.oracle.graal.nodes.java.InstanceOfNode;
-import com.oracle.graal.nodes.spi.ValueProxy;
-import com.oracle.graal.compiler.common.type.IllegalStamp;
-import com.oracle.graal.compiler.common.type.ObjectStamp;
-import com.oracle.graal.compiler.common.type.StampFactory;
-import com.oracle.graal.nodes.type.StampTool;
-import com.oracle.graal.nodes.util.GraphUtil;
-
-import java.util.IdentityHashMap;
-import java.util.Set;
+import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.extended.*;
+import com.oracle.graal.nodes.java.*;
+import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.util.*;
/**
*
@@ -65,11 +58,12 @@
*/
public final class EquationalReasoner {
- private static final DebugMetric metricInstanceOfRemoved = Debug.metric("InstanceOfRemoved");
- private static final DebugMetric metricNullCheckRemoved = Debug.metric("NullCheckRemoved");
- private static final DebugMetric metricObjectEqualsRemoved = Debug.metric("ObjectEqualsRemoved");
- private static final DebugMetric metricEquationalReasoning = Debug.metric("EquationalReasoning");
- private static final DebugMetric metricDowncasting = Debug.metric("Downcasting");
+ private static final DebugMetric metricInstanceOfRemoved = Debug.metric("FSR-InstanceOfRemoved");
+ private static final DebugMetric metricNullCheckRemoved = Debug.metric("FSR-NullCheckRemoved");
+ private static final DebugMetric metricObjectEqualsRemoved = Debug.metric("FSR-ObjectEqualsRemoved");
+ private static final DebugMetric metricEquationalReasoning = Debug.metric("FSR-EquationalReasoning");
+ private static final DebugMetric metricDowncasting = Debug.metric("FSR-Downcasting");
+ private static final DebugMetric metricNullInserted = Debug.metric("FSR-NullInserted");
private final StructuredGraph graph;
private final CanonicalizerTool tool;
@@ -87,7 +81,7 @@
* {@link com.oracle.graal.graph.NodeBitMap NodeBitMap} but in this set instead (those nodes are
* added after the {@link com.oracle.graal.graph.NodeBitMap} was obtained).
*/
- final Set added = java.util.Collections.newSetFromMap(new IdentityHashMap());
+ final Set added = newNodeIdentitySet();
/**
* The reduction of a FloatingNode performed by {@link EquationalReasoner EquationalReasoner}
@@ -97,7 +91,7 @@
* The substitutions tracked in this field become invalid as described in
* {@link #updateState(com.oracle.graal.phases.common.cfs.State) updateState(State)}
*/
- private final IdentityHashMap substs = new IdentityHashMap<>();
+ private final Map substs = newNodeIdentityMap();
public EquationalReasoner(StructuredGraph graph, CanonicalizerTool tool, LogicConstantNode trueConstant, LogicConstantNode falseConstant, ConstantNode nullConstant) {
this.graph = graph;
@@ -114,6 +108,7 @@
*/
public void forceState(State s) {
state = s;
+ assert state.repOK();
substs.clear();
added.clear();
visited = null;
@@ -235,6 +230,17 @@
// picked cached substitution
return result;
}
+ if (FlowUtil.hasLegalObjectStamp(v) && state.isNull(v)) {
+ // it's ok to return nullConstant in deverbosify unlike in downcast
+ metricNullInserted.increment();
+ return nullConstant;
+ }
+ if (v instanceof ValueProxy) {
+ return v;
+ }
+ if (!(n instanceof FloatingNode)) {
+ return n;
+ }
if ((visited != null && visited.contains(n)) || added.contains(v)) {
return v;
}
@@ -252,25 +258,13 @@
* Past this point, if we ever want `n` to be deverbosified, it must be looked-up by one of
* the cases above. One sure way to achieve that is with `rememberSubstitution(old, new)`
*/
- if (v instanceof ValueProxy) {
- return downcast(v);
- }
- if (n instanceof FloatingNode) {
- /*
- * `deverbosifyFloatingNode()` will drill down over floating inputs, when that not
- * possible anymore it resorts to calling `downcast()`. Thus it's ok to take the
- * `deverbosifyFloatingNode()` route first, as no downcasting opportunity will be
- * missed.
- */
- return deverbosifyFloatingNode((FloatingNode) n);
- }
-
- if (FlowUtil.hasLegalObjectStamp(v)) {
- return downcast(v);
- }
-
- return n;
+ /*
+ * `deverbosifyFloatingNode()` will drill down over floating inputs, when that not possible
+ * anymore it resorts to calling `downcast()`. Thus it's ok to take the
+ * `deverbosifyFloatingNode()` route first, as no downcasting opportunity will be missed.
+ */
+ return deverbosifyFloatingNode((FloatingNode) n);
}
/**
@@ -334,16 +328,7 @@
}
if (changed == null) {
assert visited.contains(f) || added.contains(f);
- if (FlowUtil.hasLegalObjectStamp(f)) {
- /*
- * No input has changed doesn't imply there's no witness to refine the
- * floating-object value.
- */
- ValueNode d = downcast(f);
- return d;
- } else {
- return f;
- }
+ return f;
}
FlowUtil.inferStampAndCheck(changed);
added.add(changed);
@@ -441,6 +426,8 @@
return baseCaseIsNullNode((IsNullNode) condition);
} else if (condition instanceof ObjectEqualsNode) {
return baseCaseObjectEqualsNode((ObjectEqualsNode) condition);
+ } else if (condition instanceof ShortCircuitOrNode) {
+ return baseCaseShortCircuitOrNode((ShortCircuitOrNode) condition);
}
}
return condition;
@@ -465,6 +452,11 @@
if (state.isNull(scrutinee)) {
metricInstanceOfRemoved.increment();
return falseConstant;
+ } else if (state.knownNotToPassInstanceOf(scrutinee, instanceOf.type())) {
+ // scrutinee turns out to be null -> falseConstant right answer
+ // scrutinee not null, but known-not-to-conform -> falseConstant
+ metricInstanceOfRemoved.increment();
+ return falseConstant;
} else if (state.isNonNull(scrutinee) && state.knownToConform(scrutinee, instanceOf.type())) {
metricInstanceOfRemoved.increment();
return trueConstant;
@@ -477,21 +469,19 @@
* performed; otherwise the unmodified argument.
*
*/
- private FloatingNode baseCaseIsNullNode(IsNullNode isNull) {
- ValueNode object = isNull.object();
+ private FloatingNode baseCaseIsNullNode(IsNullNode isNu) {
+ ValueNode object = isNu.object();
if (!FlowUtil.hasLegalObjectStamp(object)) {
- return isNull;
+ return isNu;
}
- ValueNode scrutinee = GraphUtil.unproxify(isNull.object());
- GuardingNode evidence = nonTrivialNullAnchor(scrutinee);
- if (evidence != null) {
+ if (state.isNull(object)) {
metricNullCheckRemoved.increment();
return trueConstant;
- } else if (state.isNonNull(scrutinee)) {
+ } else if (state.isNonNull(object)) {
metricNullCheckRemoved.increment();
return falseConstant;
}
- return isNull;
+ return isNu;
}
/**
@@ -515,6 +505,38 @@
}
/**
+ * The following is tried:
+ *
+ *
+ *
+ * A {@link com.oracle.graal.phases.common.cfs.Witness} that is at check-cast level level
+ * doesn't entail {@link com.oracle.graal.nodes.calc.IsNullNode} (on its own) nor
+ * {@link com.oracle.graal.nodes.java.InstanceOfNode} (also on its own) but of course it entails
+ * (IsNull || IsInstanceOf). Good thing
+ * {@link com.oracle.graal.phases.common.cfs.CastCheckExtractor} detects that very pattern.
+ *
+ * Otherwise return the unmodified argument (later on,
+ * {@link #deverbosifyFloatingNode(com.oracle.graal.nodes.calc.FloatingNode)} will attempt to
+ * simplify the {@link com.oracle.graal.nodes.ShortCircuitOrNode}).
+ *
+ *
+ * @return a {@link com.oracle.graal.nodes.LogicConstantNode}, in case a reduction was made;
+ * otherwise the unmodified argument.
+ */
+ private LogicNode baseCaseShortCircuitOrNode(ShortCircuitOrNode orNode) {
+ CastCheckExtractor cast = CastCheckExtractor.extract(orNode);
+ if (cast != null) {
+ if (state.knownToConform(cast.subject, cast.type)) {
+ return trueConstant;
+ } else if (state.knownNotToPassCheckCast(cast.subject, cast.type)) {
+ return falseConstant;
+ }
+ return orNode;
+ }
+ return orNode;
+ }
+
+ /**
* It's always ok to use "downcast(object)" instead of " object"
* because this method re-wraps the argument in a {@link com.oracle.graal.nodes.PiNode} only if
* the new stamp is strictly more refined than the original.
@@ -558,6 +580,7 @@
PiNode untrivialNull = nonTrivialNull(scrutinee);
if (untrivialNull != null) {
+ metricNullInserted.increment();
return untrivialNull;
}
@@ -646,24 +669,6 @@
}
/**
- *
- * If the argument is known null due to its stamp, there's no need to have an anchor for that
- * fact and this method returns null.
- *
- *
- *
- * Otherwise, if an anchor is found it is returned, null otherwise.
- *
@@ -680,7 +685,7 @@
*/
public PiNode nonTrivialNull(ValueNode object) {
assert FlowUtil.hasLegalObjectStamp(object);
- GuardingNode anchor = nonTrivialNullAnchor(object);
+ GuardingNode anchor = state.nonTrivialNullAnchor(object);
if (anchor == null) {
return null;
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Evidence.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Evidence.java Mon May 12 21:29:29 2014 -0700
@@ -0,0 +1,61 @@
+/*
+ * Copyright (c) 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.phases.common.cfs;
+
+import com.oracle.graal.nodes.extended.GuardingNode;
+
+public class Evidence {
+
+ public final GuardingNode success;
+ public final boolean failure;
+
+ public Evidence(GuardingNode success, boolean failure) {
+ this.success = success;
+ this.failure = failure;
+ assert repOK();
+ }
+
+ public Evidence(GuardingNode success) {
+ this(success, false);
+ }
+
+ private Evidence(boolean failure) {
+ this(null, failure);
+ }
+
+ public boolean isPositive() {
+ return success != null;
+ }
+
+ public boolean isNegative() {
+ return failure;
+ }
+
+ private boolean repOK() {
+ // either success or failure, ie boolean-XOR
+ return (success != null) != failure;
+ }
+
+ public static Evidence COUNTEREXAMPLE = new Evidence(true);
+
+}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java Mon May 12 21:29:29 2014 -0700
@@ -23,9 +23,7 @@
package com.oracle.graal.phases.common.cfs;
import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.calc.IsNullNode;
import com.oracle.graal.nodes.extended.GuardingNode;
-import com.oracle.graal.nodes.java.*;
import com.oracle.graal.phases.tiers.PhaseContext;
/**
@@ -43,7 +41,7 @@
*/
public abstract class FixedGuardReduction extends CheckCastReduction {
- public FixedGuardReduction(FixedNode start, State initialState, PhaseContext context) {
+ public FixedGuardReduction(StartNode start, State initialState, PhaseContext context) {
super(start, initialState, context);
}
@@ -99,118 +97,33 @@
return;
}
- /*
- * Attempt to eliminate the current FixedGuardNode by using another GuardingNode already in
- * scope and with equivalent condition.
- */
+ final boolean isTrue = !f.isNegated();
+ final Evidence evidence = state.outcome(isTrue, f.condition());
- GuardingNode existingGuard = f.isNegated() ? state.falseFacts.get(f.condition()) : state.trueFacts.get(f.condition());
- if (existingGuard != null) {
- // assert existingGuard instanceof FixedGuardNode;
- metricFixedGuardNodeRemoved.increment();
- f.replaceAtUsages(existingGuard.asNode());
- graph.removeFixed(f);
+ // can't produce evidence, must be information gain
+ if (evidence == null) {
+ state.addFact(isTrue, f.condition(), f);
return;
}
- final LogicNode cond = f.condition();
- final boolean isTrue = !f.isNegated();
-
- /*
- * A FixedGuardNode can only be removed provided a replacement anchor is found (so called
- * "evidence"), ie an anchor that amounts to the same combination of (negated, condition) as
- * for the FixedGuardNode at hand. Just deverbosifying the condition in place isn't
- * semantics-preserving.
- */
-
- // TODO what about isDependencyTainted
-
- if (cond instanceof IsNullNode) {
- final IsNullNode isNullNode = (IsNullNode) cond;
- if (isTrue) {
- // grab an anchor attesting nullness
- final GuardingNode replacement = reasoner.nonTrivialNullAnchor(isNullNode.object());
- if (replacement != null) {
- removeFixedGuardNode(f, replacement);
- return;
- }
- if (state.isNonNull(isNullNode.object())) {
- markFixedGuardNodeAlwaysFails(f);
- return;
- }
- // can't produce evidence, fall-through to addFact
- } else {
- // grab an anchor attesting non-nullness
- final Witness w = state.typeInfo(isNullNode.object());
- if (w != null && w.isNonNull()) {
- removeFixedGuardNode(f, w.guard());
- return;
- }
- if (state.isNull(isNullNode.object())) {
- markFixedGuardNodeAlwaysFails(f);
- return;
- }
- // can't produce evidence, fall-through to addFact
- }
- } else if (cond instanceof InstanceOfNode) {
- final InstanceOfNode iOf = (InstanceOfNode) cond;
- final Witness w = state.typeInfo(iOf.object());
- if (isTrue) {
- // grab an anchor attesting instanceof
- if (w != null) {
- if (w.isNonNull() && w.type() != null) {
- if (iOf.type().isAssignableFrom(w.type())) {
- removeFixedGuardNode(f, w.guard());
- return;
- }
- if (State.knownNotToConform(w.type(), iOf.type())) {
- markFixedGuardNodeAlwaysFails(f);
- return;
- }
- }
- }
- if (state.isNull(iOf.object())) {
- markFixedGuardNodeAlwaysFails(f);
- return;
- }
- // can't produce evidence, fall-through to addFact
- } else {
- // grab an anchor attesting not-instanceof
- // (1 of 2) attempt determining nullness
- final GuardingNode nullGuard = reasoner.nonTrivialNullAnchor(iOf.object());
- if (nullGuard != null) {
- removeFixedGuardNode(f, nullGuard);
- return;
- }
- // (2 of 2) attempt determining known-not-to-conform
- if (w != null && !w.cluelessAboutType()) {
- if (State.knownNotToConform(w.type(), iOf.type())) {
- removeFixedGuardNode(f, w.guard());
- return;
- }
- }
- // can't produce evidence, fall-through to addFact
- }
- } else if (isTrue && cond instanceof ShortCircuitOrNode) {
- CastCheckExtractor cce = CastCheckExtractor.extract(cond);
- if (cce != null && !State.isDependencyTainted(cce.subject, f)) {
- // grab an anchor attesting check-cast
- Witness w = state.typeInfo(cce.subject);
- if (w != null && w.type() != null) {
- if (cce.type.isAssignableFrom(w.type())) {
- removeFixedGuardNode(f, w.guard());
- return;
- }
- if (State.knownNotToConform(w.type(), cce.type)) {
- markFixedGuardNodeAlwaysFails(f);
- return;
- }
- }
- }
- // can't produce evidence, fall-through to addFact
+ if (evidence.isPositive()) {
+ /*
+ * A FixedGuardNode can only be removed provided a replacement anchor is found (so
+ * called "evidence"), ie an anchor that amounts to the same combination of (negated,
+ * condition) as for the FixedGuardNode at hand. Just deverbosifying the condition in
+ * place isn't semantics-preserving.
+ *
+ * Eliminate the current FixedGuardNode by using another GuardingNode already in scope,
+ * a GuardingNode that guards a condition that is at least as strong as that of the
+ * FixedGuardNode.
+ */
+ removeFixedGuardNode(f, evidence.success);
+ return;
}
- state.addFact(isTrue, cond, f);
+ assert evidence.isNegative();
+ markFixedGuardNodeAlwaysFails(f);
+
}
/**
@@ -232,9 +145,7 @@
*
simplification of side-effects free expressions, via
* {@link com.oracle.graal.phases.common.cfs.EquationalReasoner#deverbosify(com.oracle.graal.graph.Node)}
+ *
+ *
+ * at certain {@link com.oracle.graal.nodes.FixedNode}, see
+ * {@link #deverbosifyInputsInPlace(com.oracle.graal.nodes.ValueNode)}
+ *
+ * including for devirtualization, see
+ * {@link #deverbosifyInputsCopyOnWrite(com.oracle.graal.nodes.java.MethodCallTargetNode)}
+ *
*
*
simplification of control-flow:
*
@@ -76,6 +84,13 @@
*
*
*
+ *
+ * Metrics for this phase are displayed starting with FSR-prefix, their counters are
+ * hosted in {@link com.oracle.graal.phases.common.cfs.BaseReduction},
+ * {@link com.oracle.graal.phases.common.cfs.EquationalReasoner} and
+ * {@link com.oracle.graal.phases.common.cfs.State}.
+ *
+ *
* @see com.oracle.graal.phases.common.cfs.CheckCastReduction
* @see com.oracle.graal.phases.common.cfs.GuardingPiReduction
* @see com.oracle.graal.phases.common.cfs.FixedGuardReduction
@@ -83,7 +98,7 @@
*/
public class FlowSensitiveReduction extends FixedGuardReduction {
- public FlowSensitiveReduction(FixedNode start, State initialState, PhaseContext context) {
+ public FlowSensitiveReduction(StartNode start, State initialState, PhaseContext context) {
super(start, initialState, context);
}
@@ -150,6 +165,7 @@
assert !isAliveWithoutUsages(trueConstant);
assert !isAliveWithoutUsages(falseConstant);
assert !isAliveWithoutUsages(nullConstant);
+ super.finished();
}
private static boolean isAliveWithoutUsages(FloatingNode node) {
@@ -217,13 +233,8 @@
// `begin` denotes the default case of the TypeSwitchNode
return;
}
- if (state.knownNotToConform(loadHub.object(), type)) {
- postponedDeopts.addDeoptAfter(begin, UnreachedCode);
- state.impossiblePath();
- return;
- }
// it's unwarranted to assume loadHub.object() to be non-null
- // it also seems unwarranted state.trackCC(loadHub.object(), type, begin);
+ state.trackCC(loadHub.object(), type, begin);
}
}
@@ -295,9 +306,16 @@
*
*/
private MethodCallTargetNode deverbosifyInputsCopyOnWrite(MethodCallTargetNode parent) {
+ final MethodCallTargetNode.InvokeKind ik = parent.invokeKind();
+ final boolean shouldTryDevirt = (ik == MethodCallTargetNode.InvokeKind.Interface || ik == MethodCallTargetNode.InvokeKind.Virtual);
+ boolean shouldDowncastReceiver = shouldTryDevirt;
MethodCallTargetNode changed = null;
for (ValueNode i : FlowUtil.distinctValueAndConditionInputs(parent)) {
- Node j = reasoner.deverbosify(i);
+ ValueNode j = (ValueNode) reasoner.deverbosify(i);
+ if (shouldDowncastReceiver) {
+ shouldDowncastReceiver = false;
+ j = reasoner.downcast(j);
+ }
if (i != j) {
assert j != parent;
if (changed == null) {
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/GuardingPiReduction.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/GuardingPiReduction.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/GuardingPiReduction.java Mon May 12 21:29:29 2014 -0700
@@ -47,7 +47,7 @@
*/
public abstract class GuardingPiReduction extends BaseReduction {
- public GuardingPiReduction(FixedNode start, State initialState, PhaseContext context) {
+ public GuardingPiReduction(StartNode start, State initialState, PhaseContext context) {
super(start, initialState, context);
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java Mon May 12 21:29:29 2014 -0700
@@ -22,24 +22,22 @@
*/
package com.oracle.graal.phases.common.cfs;
-import com.oracle.graal.api.meta.Kind;
-import com.oracle.graal.api.meta.ResolvedJavaType;
-import com.oracle.graal.debug.Debug;
-import com.oracle.graal.debug.DebugMetric;
+import static com.oracle.graal.graph.util.CollectionsAccess.*;
+
+import java.lang.reflect.*;
+import java.util.*;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.compiler.common.type.*;
+import com.oracle.graal.debug.*;
import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.calc.IsNullNode;
-import com.oracle.graal.nodes.calc.ObjectEqualsNode;
-import com.oracle.graal.nodes.extended.GuardedNode;
-import com.oracle.graal.nodes.extended.GuardingNode;
-import com.oracle.graal.nodes.java.InstanceOfNode;
-import com.oracle.graal.nodes.spi.ValueProxy;
-import com.oracle.graal.compiler.common.type.ObjectStamp;
-import com.oracle.graal.nodes.type.StampTool;
-import com.oracle.graal.nodes.util.GraphUtil;
-import com.oracle.graal.phases.graph.MergeableState;
-
-import java.lang.reflect.Modifier;
-import java.util.*;
+import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.extended.*;
+import com.oracle.graal.nodes.java.*;
+import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.util.*;
+import com.oracle.graal.phases.graph.*;
/**
* A State instance is mutated in place as each FixedNode is visited in a basic block of
@@ -50,10 +48,10 @@
*/
public final class State extends MergeableState implements Cloneable {
- private static final DebugMetric metricTypeRegistered = Debug.metric("TypeRegistered");
- private static final DebugMetric metricNullnessRegistered = Debug.metric("NullnessRegistered");
- private static final DebugMetric metricObjectEqualsRegistered = Debug.metric("ObjectEqualsRegistered");
- private static final DebugMetric metricImpossiblePathDetected = Debug.metric("ImpossiblePathDetected");
+ private static final DebugMetric metricTypeRegistered = Debug.metric("FSR-TypeRegistered");
+ private static final DebugMetric metricNullnessRegistered = Debug.metric("FSR-NullnessRegistered");
+ private static final DebugMetric metricObjectEqualsRegistered = Debug.metric("FSR-ObjectEqualsRegistered");
+ private static final DebugMetric metricImpossiblePathDetected = Debug.metric("FSR-ImpossiblePathDetected");
/**
*
@@ -99,46 +97,47 @@
/**
*
- * This map semantically tracks "facts" (ie, properties valid for the program-point the state
- * refers to) as opposed to floating-guard-dependent properties. The
- * {@link com.oracle.graal.nodes.extended.GuardingNode} being tracked comes handy at
- * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction#visitFixedGuardNode(com.oracle.graal.nodes.FixedGuardNode)}
- * .
+ * This map tracks properties about reference-values, ie combinations of: definitely-null,
+ * known-to-be-non-null, seen-type.
*
*
*
- * On a related note, {@link #typeRefinements} also captures information the way
- * {@link #trueFacts} and {@link #falseFacts} do, including "witnessing" guards. Why not just
- * standardize on one of them, and drop the other? Because the {@link #typeRefinements} eagerly
- * aggregates information for easier querying afterwards, e.g. when producing a "downcasted"
- * value (which involves building a {@link com.oracle.graal.nodes.PiNode}, see
- * {@link EquationalReasoner#downcast(com.oracle.graal.nodes.ValueNode) downcast()}
+ * In contrast to {@link #trueFacts} and {@link #falseFacts}, this map can answer queries even
+ * though the exact {@link LogicNode} standing for such query hasn't been tracked. For example,
+ * queries about subtyping. Additionally, a {@link Witness} can combine separate pieces of
+ * information more flexibly, eg, two separate observations about non-null and check-cast are
+ * promoted to an instance-of witness.
*
* This method handles phis, by adding to the resulting state any information that can be gained
@@ -221,7 +195,7 @@
* when merging type-witnesses and known-null maps.
*
*/
- private void mergePhis(MergeNode merge, List withStates, IdentityHashMap newKnownPhiTypes, IdentityHashMap newKnownNullPhis) {
+ private void mergePhis(MergeNode merge, List withStates, Map newKnownPhiTypes) {
if (merge instanceof LoopBeginNode) {
return;
@@ -244,20 +218,21 @@
ObjectStamp phiStamp = (ObjectStamp) phi.stamp();
ObjectStamp nonPollutedStamp = (ObjectStamp) StampTool.meet(reachingValues);
Witness w = new Witness(nonPollutedStamp, merge);
- if (FlowUtil.isMorePrecise(w.type(), phiStamp.type())) {
+ if (w.isNull() && !phiStamp.alwaysNull()) {
+ // precision gain: null
+ newKnownPhiTypes.put(phi, w);
+ } else if (FlowUtil.isMorePrecise(w.type(), phiStamp.type())) {
// precision gain regarding type
newKnownPhiTypes.put(phi, w);
// confirm no precision loss regarding nullness
assert implies(phiStamp.nonNull(), w.isNonNull());
+ assert implies(phiStamp.alwaysNull(), w.isNull());
} else if (w.isNonNull() && !phiStamp.nonNull()) {
- // precision gain regarding nullness
+ // precision gain: non-null
newKnownPhiTypes.put(phi, w);
// confirm no precision loss regarding type
assert !FlowUtil.isMorePrecise(phiStamp.type(), w.type());
}
- if (nonPollutedStamp.alwaysNull()) {
- newKnownNullPhis.put(phi, merge);
- }
}
}
@@ -284,27 +259,27 @@
if (isUnreachable) {
typeRefinements.clear();
- knownNull.clear();
trueFacts.clear();
falseFacts.clear();
return true;
}
// may also get updated in a moment, during processing of phi nodes.
- IdentityHashMap newKnownTypes = mergeKnownTypes(merge, withReachableStates);
+ Map newKnownTypes = mergeKnownTypes(merge, withReachableStates);
// may also get updated in a moment, during processing of phi nodes.
- IdentityHashMap newKnownNull = mergeKnownNull(merge, withReachableStates);
- mergePhis(merge, withStates, newKnownTypes, newKnownNull);
+ mergePhis(merge, withStates, newKnownTypes);
this.typeRefinements = newKnownTypes;
- this.knownNull = newKnownNull;
this.trueFacts = mergeTrueFacts(withReachableStates, merge);
this.falseFacts = mergeFalseFacts(withReachableStates, merge);
+
+ assert repOK();
+
return true;
}
- private IdentityHashMap mergeTrueFacts(ArrayList withReachableStates, GuardingNode merge) {
- IdentityHashMap newTrueConditions = new IdentityHashMap<>();
+ private Map mergeTrueFacts(ArrayList withReachableStates, GuardingNode merge) {
+ Map newTrueConditions = newNodeIdentityMap();
for (Map.Entry entry : trueFacts.entrySet()) {
LogicNode check = entry.getKey();
GuardingNode guard = entry.getValue();
@@ -326,8 +301,8 @@
return newTrueConditions;
}
- private IdentityHashMap mergeFalseFacts(ArrayList withReachableStates, GuardingNode merge) {
- IdentityHashMap newFalseConditions = new IdentityHashMap<>();
+ private Map mergeFalseFacts(ArrayList withReachableStates, GuardingNode merge) {
+ Map newFalseConditions = newNodeIdentityMap();
for (Map.Entry entry : falseFacts.entrySet()) {
LogicNode check = entry.getKey();
GuardingNode guard = entry.getValue();
@@ -362,7 +337,12 @@
*/
public boolean isNull(ValueNode object) {
assert FlowUtil.hasLegalObjectStamp(object);
- return StampTool.isObjectAlwaysNull(object) || knownNull.containsKey(GraphUtil.unproxify(object));
+ if (StampTool.isObjectAlwaysNull(object)) {
+ return true;
+ }
+ ValueNode scrutinee = GraphUtil.unproxify(object);
+ Witness w = typeRefinements.get(scrutinee);
+ return (w != null) && w.isNull();
}
/**
@@ -393,7 +373,8 @@
}
/**
- * @return true iff the argument is known to stand for an object conforming to the given type.
+ * @return true iff the argument definitely stands for an object-value that conforms to the
+ * given type.
*/
public boolean knownToConform(ValueNode object, ResolvedJavaType to) {
assert FlowUtil.hasLegalObjectStamp(object);
@@ -415,14 +396,20 @@
}
/**
- * @return true iff the argument is known to stand for an object that definitely does not
- * conform to the given type.
+ * @return true iff the argument is known to stand for an object that is definitely non-null and
+ * moreover does not conform to the given type.
*/
- public boolean knownNotToConform(ValueNode object, ResolvedJavaType to) {
+ public boolean knownNotToPassCheckCast(ValueNode object, ResolvedJavaType to) {
assert FlowUtil.hasLegalObjectStamp(object);
assert !to.isPrimitive();
final ValueNode scrutinee = GraphUtil.unproxify(object);
if (isNull(scrutinee)) {
+ // known-null means it conforms to whatever `to`
+ // and thus passes the check-cast
+ return false;
+ }
+ if (!isNonNull(scrutinee)) {
+ // unless `null` can be ruled out, a positive answer isn't safe
return false;
}
ResolvedJavaType stampType = StampTool.typeOrNull(object);
@@ -437,6 +424,34 @@
return false;
}
+ /**
+ * @return true iff the argument is known to stand for an object that definitely does not
+ * conform to the given type (no matter whether the object turns out to be null or
+ * non-null).
+ */
+ public boolean knownNotToPassInstanceOf(ValueNode object, ResolvedJavaType to) {
+ assert FlowUtil.hasLegalObjectStamp(object);
+ assert !to.isPrimitive();
+ final ValueNode scrutinee = GraphUtil.unproxify(object);
+ if (isNull(scrutinee)) {
+ return true;
+ }
+ ResolvedJavaType stampType = StampTool.typeOrNull(object);
+ if (stampType != null && knownNotToConform(stampType, to)) {
+ // object turns out to be null, positive answer is correct
+ // object turns out non-null, positive answer is also correct
+ return true;
+ }
+ Witness w = typeInfo(scrutinee);
+ boolean witnessAnswer = w != null && !w.cluelessAboutType() && knownNotToConform(w.type(), to);
+ if (witnessAnswer) {
+ // object turns out to be null, positive answer is correct
+ // object turns out non-null, positive answer is also correct
+ return true;
+ }
+ return false;
+ }
+
// @formatter:off
/**
* \ | | | |
@@ -526,6 +541,7 @@
Witness w = getOrElseAddTypeInfo(object);
if (w.trackNN(anchor)) {
versionNr++;
+ assert repOK();
return true;
}
return false;
@@ -558,6 +574,7 @@
if (w.trackCC(observed, anchor)) {
versionNr++;
metricTypeRegistered.increment();
+ assert repOK();
return true;
}
return false;
@@ -584,6 +601,7 @@
if (w.trackIO(observed, anchor)) {
versionNr++;
metricTypeRegistered.increment();
+ assert repOK();
return true;
}
return false;
@@ -600,7 +618,7 @@
*
*
*/
- private void addFactPrimordial(LogicNode condition, IdentityHashMap to, GuardingNode anchor) {
+ private void addFactPrimordial(LogicNode condition, Map to, GuardingNode anchor) {
assert condition != null;
if (!to.containsKey(condition)) {
versionNr++;
@@ -665,6 +683,7 @@
} else {
addFactPrimordial(condition, isTrue ? trueFacts : falseFacts, anchor);
}
+ assert repOK();
}
/**
@@ -675,7 +694,7 @@
private void addFactInstanceOf(boolean isTrue, InstanceOfNode instanceOf, GuardingNode anchor) {
ValueNode object = instanceOf.object();
if (isTrue) {
- if (knownNotToConform(object, instanceOf.type())) {
+ if (knownNotToPassInstanceOf(object, instanceOf.type())) {
impossiblePath();
return;
}
@@ -757,25 +776,27 @@
return;
}
assert anchor instanceof FixedNode;
- ValueNode original = GraphUtil.unproxify(value);
- boolean wasNull = isNull(original);
- boolean wasNonNull = isNonNull(original);
+ ValueNode scrutinee = GraphUtil.unproxify(value);
+ boolean wasNull = isNull(scrutinee);
+ boolean wasNonNull = isNonNull(scrutinee);
if (isNull) {
if (wasNonNull) {
impossiblePath();
} else {
metricNullnessRegistered.increment();
versionNr++;
- knownNull.put(original, anchor);
+ Witness w = getOrElseAddTypeInfo(scrutinee);
+ w.trackDN(anchor);
}
} else {
if (wasNull) {
impossiblePath();
} else {
metricNullnessRegistered.increment();
- trackNN(original, anchor);
+ trackNN(scrutinee, anchor);
}
}
+ assert repOK();
}
/**
@@ -808,9 +829,187 @@
versionNr = 0;
isUnreachable = false;
typeRefinements.clear();
- knownNull.clear();
trueFacts.clear();
falseFacts.clear();
}
+ /**
+ *
+ * If the argument is known null due to its stamp, there's no need to have an anchor for that
+ * fact and this method returns null.
+ *
+ *
+ *
+ * Otherwise, if an anchor is found it is returned, null otherwise.
+ *
+ */
+ public GuardingNode nonTrivialNullAnchor(ValueNode object) {
+ assert FlowUtil.hasLegalObjectStamp(object);
+ if (StampTool.isObjectAlwaysNull(object)) {
+ return null;
+ }
+ ValueNode scrutinee = GraphUtil.unproxify(object);
+ Witness w = typeRefinements.get(scrutinee);
+ if (w != null && w.isNull()) {
+ return w.guard();
+ }
+ return null;
+ }
+
+ /**
+ * This method:
+ *
+ *
+ * attempts to find an existing {@link com.oracle.graal.nodes.extended.GuardingNode} that
+ * implies the property stated by the arguments. If found, returns it as positive evidence.
+ *
+ * otherwise, if the property of interest is known not to hold, negative evidence is returned.
+ *
+ * otherwise, null is returned.
+ *
+ */
+ public Evidence outcome(boolean isTrue, LogicNode cond) {
+
+ // attempt to find an anchor for the condition of interest, verbatim
+ if (isTrue) {
+ GuardingNode existingGuard = trueFacts.get(cond);
+ if (existingGuard != null) {
+ return new Evidence(existingGuard);
+ }
+ if (falseFacts.containsKey(cond)) {
+ return Evidence.COUNTEREXAMPLE;
+ }
+ } else {
+ GuardingNode existingGuard = falseFacts.get(cond);
+ if (existingGuard != null) {
+ return new Evidence(existingGuard);
+ }
+ if (trueFacts.containsKey(cond)) {
+ return Evidence.COUNTEREXAMPLE;
+ }
+ }
+
+ if (cond instanceof IsNullNode) {
+ return outcomeIsNullNode(isTrue, (IsNullNode) cond);
+ }
+
+ if (cond instanceof InstanceOfNode) {
+ return outcomeInstanceOfNode(isTrue, (InstanceOfNode) cond);
+ }
+
+ if (cond instanceof ShortCircuitOrNode) {
+ return outcomeShortCircuitOrNode(isTrue, (ShortCircuitOrNode) cond);
+ }
+
+ // can't produce evidence
+ return null;
+ }
+
+ /**
+ * Utility method for {@link #outcome(boolean, com.oracle.graal.nodes.LogicNode)}
+ */
+ private Evidence outcomeIsNullNode(boolean isTrue, IsNullNode isNullNode) {
+ if (isTrue) {
+ // grab an anchor attesting nullness
+ final GuardingNode replacement = nonTrivialNullAnchor(isNullNode.object());
+ if (replacement != null) {
+ return new Evidence(replacement);
+ }
+ if (isNonNull(isNullNode.object())) {
+ return Evidence.COUNTEREXAMPLE;
+ }
+ } else {
+ // grab an anchor attesting non-nullness
+ final Witness w = typeInfo(isNullNode.object());
+ if (w != null && w.isNonNull()) {
+ return new Evidence(w.guard());
+ }
+ if (isNull(isNullNode.object())) {
+ return Evidence.COUNTEREXAMPLE;
+ }
+ }
+ // can't produce evidence
+ return null;
+ }
+
+ /**
+ * Utility method for {@link #outcome(boolean, com.oracle.graal.nodes.LogicNode)}
+ */
+ private Evidence outcomeInstanceOfNode(boolean isTrue, InstanceOfNode iOf) {
+ final Witness w = typeInfo(iOf.object());
+ if (isTrue) {
+ if (isNull(iOf.object())) {
+ return Evidence.COUNTEREXAMPLE;
+ }
+ // grab an anchor attesting instanceof
+ if ((w != null) && (w.type() != null)) {
+ if (w.isNonNull()) {
+ if (iOf.type().isAssignableFrom(w.type())) {
+ return new Evidence(w.guard());
+ }
+ }
+ if (State.knownNotToConform(w.type(), iOf.type())) {
+ // null -> fails instanceof
+ // non-null but non-conformant -> also fails instanceof
+ return Evidence.COUNTEREXAMPLE;
+ }
+ }
+ } else {
+ // grab an anchor attesting not-instanceof
+ // (1 of 2) attempt determining nullness
+ final GuardingNode nullGuard = nonTrivialNullAnchor(iOf.object());
+ if (nullGuard != null) {
+ return new Evidence(nullGuard);
+ }
+ // (2 of 2) attempt determining known-not-to-conform
+ if (w != null && !w.cluelessAboutType()) {
+ if (State.knownNotToConform(w.type(), iOf.type())) {
+ return new Evidence(w.guard());
+ }
+ }
+ }
+ // can't produce evidence
+ return null;
+ }
+
+ /**
+ * Utility method for {@link #outcome(boolean, com.oracle.graal.nodes.LogicNode)}
+ */
+ private Evidence outcomeShortCircuitOrNode(boolean isTrue, ShortCircuitOrNode orNode) {
+ if (!isTrue) {
+ // too tricky to reason about
+ return null;
+ }
+ CastCheckExtractor cce = CastCheckExtractor.extract(orNode);
+ if (cce != null) {
+ // grab an anchor attesting check-cast
+ Witness w = typeInfo(cce.subject);
+ if (w != null && w.type() != null) {
+ if (cce.type.isAssignableFrom(w.type())) {
+ return new Evidence(w.guard());
+ }
+ if (isNonNull(cce.subject) && State.knownNotToConform(w.type(), cce.type)) {
+ return Evidence.COUNTEREXAMPLE;
+ }
+ }
+ }
+ // search for positive-evidence for the first or-input
+ Evidence evidenceX = outcome(!orNode.isXNegated(), orNode.getX());
+ if (evidenceX != null && evidenceX.isPositive()) {
+ return evidenceX;
+ }
+ // search for positive-evidence for the second or-input
+ Evidence evidenceY = outcome(!orNode.isYNegated(), orNode.getY());
+ if (evidenceY != null && evidenceY.isPositive()) {
+ return evidenceY;
+ }
+ // check for contradictions on both or-inputs
+ if (evidenceX != null && evidenceY != null) {
+ assert evidenceX.isNegative() && evidenceY.isNegative();
+ return Evidence.COUNTEREXAMPLE;
+ }
+ // can't produce evidence
+ return null;
+ }
+
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Witness.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Witness.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Witness.java Mon May 12 21:29:29 2014 -0700
@@ -86,7 +86,8 @@
CLUELESS,
NN,
CC,
- IO
+ IO,
+ DN
}
private boolean atNonNull() {
@@ -101,6 +102,10 @@
return level == LEVEL.IO;
}
+ private boolean atDefinitelyNull() {
+ return level == LEVEL.DN;
+ }
+
private void transition(LEVEL to, GuardingNode newAnchor) {
this.level = to;
this.gn = newAnchor;
@@ -122,37 +127,41 @@
public Witness(ObjectStamp stamp, GuardingNode anchor) {
assert stamp.isLegal();
assert anchor != null;
- boolean isNonIface = (stamp.type() != null && !stamp.type().isInterface());
- if (stamp.nonNull()) {
- if (isNonIface) {
- seen = stamp.type();
- transition(LEVEL.IO, anchor);
+ if (stamp.alwaysNull()) {
+ // seen left null
+ transition(LEVEL.DN, anchor);
+ } else {
+ boolean isNonIface = (stamp.type() != null && !stamp.type().isInterface());
+ if (stamp.nonNull()) {
+ if (isNonIface) {
+ seen = stamp.type();
+ transition(LEVEL.IO, anchor);
+ } else {
+ seen = null;
+ transition(LEVEL.NN, anchor);
+ }
} else {
- seen = null;
- transition(LEVEL.NN, anchor);
- }
- } else {
- if (isNonIface) {
- seen = stamp.type();
- transition(LEVEL.CC, anchor);
- } else {
- seen = null;
- transition(LEVEL.CLUELESS, null);
- assert clueless();
+ if (isNonIface) {
+ seen = stamp.type();
+ transition(LEVEL.CC, anchor);
+ } else {
+ seen = null;
+ transition(LEVEL.CLUELESS, null);
+ assert clueless();
+ }
}
}
assert repOK();
}
- /**
- * Type-witnesses aren't tracked for known-to-be-null. Therefore, although method
- * {@link #isNonNull() isNonNull()} can be found in this class there's on purpose no companion
- * isNull() .
- */
public boolean isNonNull() {
return atNonNull() || atInstanceOf();
}
+ public boolean isNull() {
+ return atDefinitelyNull();
+ }
+
/**
* The most precise type known so far about the scrutinee. (Please notice that nothing can be
* deduced about the non-nullness-status of the scrutinee from invoking this method alone).
@@ -163,7 +172,7 @@
public ObjectStamp asStamp() {
boolean isKnownExact = (seen != null && seen.equals(seen.asExactType()));
- return new ObjectStamp(seen, isKnownExact, isNonNull(), false);
+ return new ObjectStamp(seen, isKnownExact, isNonNull(), isNull());
}
private LEVEL level = LEVEL.CLUELESS;
@@ -219,15 +228,14 @@
assert level == LEVEL.CLUELESS;
return true;
}
- if (level == LEVEL.NN) {
+ if (atNonNull() || atDefinitelyNull()) {
assert seen == null;
}
if (seen != null) {
assert !seen.isInterface();
assert !seen.isPrimitive();
}
- boolean gnOK = gn instanceof BeginNode || gn instanceof LoopExitNode || gn instanceof MergeNode || gn instanceof FixedGuardNode;
- assert gnOK;
+ assert gn instanceof BeginNode || gn instanceof LoopExitNode || gn instanceof MergeNode || gn instanceof FixedGuardNode;
return true;
}
@@ -235,7 +243,7 @@
* Helper method for readability in complex conditions.
*/
public boolean clueless() {
- return cluelessAboutType() && cluelessAboutNonNullness();
+ return cluelessAboutType() && cluelessAboutNullity();
}
/**
@@ -249,8 +257,8 @@
/**
* Helper method for readability in complex conditions.
*/
- public boolean cluelessAboutNonNullness() {
- return !atNonNull() && !atInstanceOf();
+ public boolean cluelessAboutNullity() {
+ return !atNonNull() && !atInstanceOf() && !atDefinitelyNull();
}
/**
@@ -276,6 +284,9 @@
* @return whether the state was updated (iff the observation adds any new information)
*/
private boolean refinesSeenType(ResolvedJavaType observed) {
+ if (isNull()) {
+ return false;
+ }
if (cluelessAboutType() || FlowUtil.isMorePrecise(observed, seen)) {
seen = observed;
return true;
@@ -294,6 +305,7 @@
*/
public boolean trackNN(GuardingNode anchor) {
assert repOK();
+ assert !isNull();
try {
if (atInstanceOf()) {
return false;
@@ -313,6 +325,29 @@
}
/**
+ * Updates this {@link Witness Witness} to account for an observation about the scrutinee being
+ * null.
+ *
+ * @return whether this {@link Witness Witness} was updated (iff the observation adds any new
+ * information)
+ */
+ public boolean trackDN(GuardingNode anchor) {
+ assert repOK();
+ assert !isNonNull();
+ try {
+ if (atDefinitelyNull()) {
+ return false;
+ }
+ assert level == LEVEL.CLUELESS || atCheckCast();
+ seen = null;
+ transition(LEVEL.DN, anchor);
+ return true;
+ } finally {
+ assert repOK();
+ }
+ }
+
+ /**
* Updates this {@link Witness Witness} to account for an observation about the scrutinee
* conforming to the provided type. In case instanceof was observed,
* {@link #trackIO(com.oracle.graal.api.meta.ResolvedJavaType, com.oracle.graal.nodes.extended.GuardingNode)
@@ -366,6 +401,7 @@
*/
public boolean trackIO(ResolvedJavaType observed, GuardingNode anchor) {
assert repOK();
+ assert !isNull();
try {
boolean gotMorePreciseType = refinesSeenType(observed);
if (!atInstanceOf() || gotMorePreciseType) {
@@ -405,12 +441,62 @@
return;
}
+ // preserve guarding node only if matches other, otherwise settle on `merge`
+ final GuardingNode resultGuard = (guard() == that.guard()) ? guard() : merge;
+
+ if (isNull()) {
+ switch (that.level) {
+ case CLUELESS:
+ case NN:
+ // lose is-null status, gain nothing
+ level = LEVEL.CLUELESS;
+ seen = null;
+ break;
+ case CC:
+ case IO:
+ // demote to check-cast
+ level = LEVEL.CC;
+ seen = that.seen;
+ break;
+ case DN:
+ // keep is-null status
+ }
+ gn = resultGuard;
+ return;
+ }
+
+ if (that.isNull()) {
+ /*
+ * Same decisions as above (based on this-being-null and that-level) are now made based
+ * on (that-being-null and this-level). Because merge is commutative.
+ */
+ switch (level) {
+ case CLUELESS:
+ case NN:
+ // lose is-null status, gain nothing
+ level = LEVEL.CLUELESS;
+ seen = null;
+ break;
+ case CC:
+ break;
+ case IO:
+ // demote to check-cast
+ level = LEVEL.CC;
+ // keep this.seen as-is
+ break;
+ case DN:
+ // keep is-null status
+ }
+ gn = resultGuard;
+ return;
+ }
+
+ // by now we know neither this nor that are known-to-be-null
+ assert !isNull() && !that.isNull();
+
// umbrella type over the observations from both witnesses
ResolvedJavaType newSeen = (seen == null || that.seen == null) ? null : FlowUtil.widen(seen, that.seen);
- // preserve guarding node only if matches other, otherwise settle on `merge`
- final GuardingNode resultGuard = guard() == that.guard() ? guard() : merge;
-
/*
* guarantee on (both conformance and non-nullness) required from each input in order for
* the result to be able to offer such guarantee
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/ComputeInliningRelevance.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/ComputeInliningRelevance.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/ComputeInliningRelevance.java Mon May 12 21:29:29 2014 -0700
@@ -22,6 +22,8 @@
*/
package com.oracle.graal.phases.common.inlining;
+import static com.oracle.graal.graph.util.CollectionsAccess.*;
+
import java.util.*;
import java.util.function.*;
@@ -46,7 +48,7 @@
* Node relevances are pre-computed for all invokes if the graph contains loops. If there are no
* loops, the computation happens lazily based on {@link #rootScope}.
*/
- private IdentityHashMap nodeRelevances;
+ private Map nodeRelevances;
/**
* This scope is non-null if (and only if) there are no loops in the graph. In this case, the
* root scope is used to compute invoke relevances on the fly.
@@ -69,10 +71,10 @@
rootScope = new Scope(graph.start(), null);
} else {
if (nodeRelevances == null) {
- nodeRelevances = new IdentityHashMap<>(EXPECTED_MIN_INVOKE_COUNT + graph.getNodeCount() / EXPECTED_INVOKE_RATIO);
+ nodeRelevances = newNodeIdentityMap(EXPECTED_MIN_INVOKE_COUNT + graph.getNodeCount() / EXPECTED_INVOKE_RATIO);
}
NodeWorkList workList = graph.createNodeWorkList();
- IdentityHashMap loops = new IdentityHashMap<>(EXPECTED_LOOP_COUNT);
+ Map loops = newNodeIdentityMap(EXPECTED_LOOP_COUNT);
loops.put(null, new Scope(graph.start(), null));
for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.class)) {
@@ -97,7 +99,7 @@
* Determines the parent of the given loop and creates a {@link Scope} object for each one. This
* method will call itself recursively if no {@link Scope} for the parent loop exists.
*/
- private Scope createLoopScope(LoopBeginNode loopBegin, IdentityHashMap loops) {
+ private Scope createLoopScope(LoopBeginNode loopBegin, Map loops) {
Scope scope = loops.get(loopBegin);
if (scope == null) {
final Scope parent;
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/InliningIterator.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/InliningIterator.java Mon May 12 21:29:29 2014 -0700
@@ -0,0 +1,130 @@
+/*
+ * 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.graal.phases.common.inlining;
+
+import com.oracle.graal.graph.Node;
+import com.oracle.graal.graph.NodeBitMap;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.java.MethodCallTargetNode;
+
+import java.util.ArrayDeque;
+import java.util.Deque;
+import java.util.LinkedList;
+
+/**
+ * Given a graph, visit all fixed nodes in dominator-based order, collecting in the process the
+ * {@link Invoke} nodes with {@link MethodCallTargetNode}. Such list of callsites is returned by
+ * {@link #apply()}
+ */
+class InliningIterator {
+
+ private final StartNode start;
+ private final Deque nodeQueue;
+ private final NodeBitMap queuedNodes;
+
+ public InliningIterator(StructuredGraph graph) {
+ this.start = graph.start();
+ this.nodeQueue = new ArrayDeque<>();
+ this.queuedNodes = graph.createNodeBitMap();
+ assert start.isAlive();
+ }
+
+ public LinkedList apply() {
+ LinkedList invokes = new LinkedList<>();
+ FixedNode current;
+ forcedQueue(start);
+
+ while ((current = nextQueuedNode()) != null) {
+ assert current.isAlive();
+
+ if (current instanceof Invoke && ((Invoke) current).callTarget() instanceof MethodCallTargetNode) {
+ if (current != start) {
+ invokes.addLast((Invoke) current);
+ }
+ queueSuccessors(current);
+ } else if (current instanceof LoopBeginNode) {
+ queueSuccessors(current);
+ } else if (current instanceof LoopEndNode) {
+ // nothing to do
+ } else if (current instanceof MergeNode) {
+ queueSuccessors(current);
+ } else if (current instanceof FixedWithNextNode) {
+ queueSuccessors(current);
+ } else if (current instanceof EndNode) {
+ queueMerge((EndNode) current);
+ } else if (current instanceof ControlSinkNode) {
+ // nothing to do
+ } else if (current instanceof ControlSplitNode) {
+ queueSuccessors(current);
+ } else {
+ assert false : current;
+ }
+ }
+
+ return invokes;
+ }
+
+ private void queueSuccessors(FixedNode x) {
+ for (Node node : x.successors()) {
+ queue(node);
+ }
+ }
+
+ private void queue(Node node) {
+ if (node != null && !queuedNodes.isMarked(node)) {
+ forcedQueue(node);
+ }
+ }
+
+ private void forcedQueue(Node node) {
+ queuedNodes.mark(node);
+ nodeQueue.addFirst((FixedNode) node);
+ }
+
+ private FixedNode nextQueuedNode() {
+ if (nodeQueue.isEmpty()) {
+ return null;
+ }
+
+ FixedNode result = nodeQueue.removeFirst();
+ assert queuedNodes.isMarked(result);
+ return result;
+ }
+
+ private void queueMerge(AbstractEndNode end) {
+ MergeNode merge = end.merge();
+ if (!queuedNodes.isMarked(merge) && visitedAllEnds(merge)) {
+ queuedNodes.mark(merge);
+ nodeQueue.add(merge);
+ }
+ }
+
+ private boolean visitedAllEnds(MergeNode merge) {
+ for (int i = 0; i < merge.forwardEndCount(); i++) {
+ if (!queuedNodes.isMarked(merge.forwardEndAt(i))) {
+ return false;
+ }
+ }
+ return true;
+ }
+}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/InliningPhase.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/InliningPhase.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/InliningPhase.java Mon May 12 21:29:29 2014 -0700
@@ -477,106 +477,13 @@
}
}
- private static class InliningIterator {
-
- private final FixedNode start;
- private final Deque nodeQueue;
- private final NodeBitMap queuedNodes;
-
- public InliningIterator(FixedNode start, NodeBitMap visitedFixedNodes) {
- this.start = start;
- this.nodeQueue = new ArrayDeque<>();
- this.queuedNodes = visitedFixedNodes;
- assert start.isAlive();
- }
-
- public LinkedList apply() {
- LinkedList invokes = new LinkedList<>();
- FixedNode current;
- forcedQueue(start);
-
- while ((current = nextQueuedNode()) != null) {
- assert current.isAlive();
-
- if (current instanceof Invoke && ((Invoke) current).callTarget() instanceof MethodCallTargetNode) {
- if (current != start) {
- invokes.addLast((Invoke) current);
- }
- queueSuccessors(current);
- } else if (current instanceof LoopBeginNode) {
- queueSuccessors(current);
- } else if (current instanceof LoopEndNode) {
- // nothing todo
- } else if (current instanceof MergeNode) {
- queueSuccessors(current);
- } else if (current instanceof FixedWithNextNode) {
- queueSuccessors(current);
- } else if (current instanceof EndNode) {
- queueMerge((EndNode) current);
- } else if (current instanceof ControlSinkNode) {
- // nothing todo
- } else if (current instanceof ControlSplitNode) {
- queueSuccessors(current);
- } else {
- assert false : current;
- }
- }
-
- return invokes;
- }
-
- private void queueSuccessors(FixedNode x) {
- for (Node node : x.successors()) {
- queue(node);
- }
- }
-
- private void queue(Node node) {
- if (node != null && !queuedNodes.isMarked(node)) {
- forcedQueue(node);
- }
- }
-
- private void forcedQueue(Node node) {
- queuedNodes.mark(node);
- nodeQueue.addFirst((FixedNode) node);
- }
-
- private FixedNode nextQueuedNode() {
- if (nodeQueue.isEmpty()) {
- return null;
- }
-
- FixedNode result = nodeQueue.removeFirst();
- assert queuedNodes.isMarked(result);
- return result;
- }
-
- private void queueMerge(AbstractEndNode end) {
- MergeNode merge = end.merge();
- if (!queuedNodes.isMarked(merge) && visitedAllEnds(merge)) {
- queuedNodes.mark(merge);
- nodeQueue.add(merge);
- }
- }
-
- private boolean visitedAllEnds(MergeNode merge) {
- for (int i = 0; i < merge.forwardEndCount(); i++) {
- if (!queuedNodes.isMarked(merge.forwardEndAt(i))) {
- return false;
- }
- }
- return true;
- }
- }
-
/**
* Holds the data for building the callee graphs recursively: graphs and invocations (each
* invocation can have multiple graphs).
*/
static class InliningData {
- private static final GraphInfo DummyGraphInfo = new GraphInfo(null, new LinkedList(), 1.0, 1.0);
+ private static final GraphInfo DummyGraphInfo = new GraphInfo(null, 1.0, 1.0);
/**
* Call hierarchy from outer most call (i.e., compilation unit) to inner most callee.
@@ -601,10 +508,7 @@
public void pushGraph(StructuredGraph graph, double probability, double relevance) {
assert !contains(graph);
- NodeBitMap visitedFixedNodes = graph.createNodeBitMap();
- LinkedList invokes = new InliningIterator(graph.start(), visitedFixedNodes).apply();
- assert invokes.size() == count(graph.getInvokes());
- graphQueue.push(new GraphInfo(graph, invokes, probability, relevance));
+ graphQueue.push(new GraphInfo(graph, probability, relevance));
assert graphQueue.size() <= maxGraphs;
}
@@ -712,16 +616,6 @@
}
return false;
}
-
- private static int count(Iterable invokes) {
- int count = 0;
- Iterator iterator = invokes.iterator();
- while (iterator.hasNext()) {
- iterator.next();
- count++;
- }
- return count;
- }
}
private static class MethodInvocation {
@@ -803,13 +697,19 @@
private final ToDoubleFunction probabilities;
private final ComputeInliningRelevance computeInliningRelevance;
- public GraphInfo(StructuredGraph graph, LinkedList invokes, double probability, double relevance) {
+ public GraphInfo(StructuredGraph graph, double probability, double relevance) {
this.graph = graph;
- this.remainingInvokes = invokes;
+ if (graph == null) {
+ this.remainingInvokes = new LinkedList<>();
+ } else {
+ LinkedList invokes = new InliningIterator(graph).apply();
+ assert invokes.size() == count(graph.getInvokes());
+ this.remainingInvokes = invokes;
+ }
this.probability = probability;
this.relevance = relevance;
- if (graph != null && (graph.hasNode(InvokeNode.class) || graph.hasNode(InvokeWithExceptionNode.class))) {
+ if (graph != null && !remainingInvokes.isEmpty()) {
probabilities = new FixedNodeProbabilityCache();
computeInliningRelevance = new ComputeInliningRelevance(graph, probabilities);
computeProbabilities();
@@ -819,6 +719,16 @@
}
}
+ private static int count(Iterable invokes) {
+ int count = 0;
+ Iterator iterator = invokes.iterator();
+ while (iterator.hasNext()) {
+ iterator.next();
+ count++;
+ }
+ return count;
+ }
+
/**
* Gets the method associated with the {@linkplain #graph() graph} represented by this
* object.
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases/src/com/oracle/graal/phases/BasePhase.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/BasePhase.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/BasePhase.java Mon May 12 21:29:29 2014 -0700
@@ -26,6 +26,7 @@
import com.oracle.graal.debug.*;
import com.oracle.graal.debug.Debug.Scope;
+import com.oracle.graal.debug.DebugMemUseTracker.Closeable;
import com.oracle.graal.debug.internal.*;
import com.oracle.graal.nodes.*;
@@ -40,6 +41,7 @@
private final DebugTimer phaseTimer;
private final DebugMetric phaseMetric;
+ private final DebugMemUseTracker phaseMemUseTracker;
private static final Pattern NAME_PATTERN = Pattern.compile("[A-Z][A-Za-z0-9]+");
@@ -51,6 +53,7 @@
protected BasePhase() {
phaseTimer = Debug.timer("PhaseTime_%s", getClass());
phaseMetric = Debug.metric("PhaseCount_%s", getClass());
+ phaseMemUseTracker = Debug.memUseTracker("PhaseMemUse_%s", getClass());
}
protected BasePhase(String name) {
@@ -58,6 +61,7 @@
this.name = name;
phaseTimer = Debug.timer("PhaseTime_%s", getClass());
phaseMetric = Debug.metric("PhaseCount_%s", getClass());
+ phaseMemUseTracker = Debug.memUseTracker("PhaseMemUse_%s", getClass());
}
protected CharSequence getDetailedName() {
@@ -69,7 +73,7 @@
}
public final void apply(final StructuredGraph graph, final C context, final boolean dumpGraph) {
- try (TimerCloseable a = phaseTimer.start(); Scope s = Debug.scope(getClass(), this)) {
+ try (TimerCloseable a = phaseTimer.start(); Scope s = Debug.scope(getClass(), this); Closeable c = phaseMemUseTracker.start()) {
BasePhase.this.run(graph, context);
phaseMetric.increment();
if (dumpGraph && Debug.isDumpEnabled()) {
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/FixedNodeProbabilityCache.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/FixedNodeProbabilityCache.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/FixedNodeProbabilityCache.java Mon May 12 21:29:29 2014 -0700
@@ -22,6 +22,8 @@
*/
package com.oracle.graal.phases.graph;
+import static com.oracle.graal.graph.util.CollectionsAccess.*;
+
import java.util.*;
import java.util.function.*;
@@ -37,7 +39,7 @@
private static final DebugMetric metricComputeNodeProbability = Debug.metric("ComputeNodeProbability");
- private final IdentityHashMap cache = new IdentityHashMap<>();
+ private final Map cache = newIdentityMap();
public double applyAsDouble(FixedNode node) {
metricComputeNodeProbability.increment();
@@ -64,7 +66,7 @@
double probability;
if (current.predecessor() == null) {
if (current instanceof MergeNode) {
- probability = ((MergeNode) current).forwardEnds().stream().mapToDouble(end -> applyAsDouble(end)).sum();
+ probability = ((MergeNode) current).forwardEnds().stream().mapToDouble(this::applyAsDouble).sum();
if (current instanceof LoopBeginNode) {
probability *= ((LoopBeginNode) current).loopFrequency();
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/PostOrderNodeIterator.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/PostOrderNodeIterator.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/PostOrderNodeIterator.java Mon May 12 21:29:29 2014 -0700
@@ -25,6 +25,7 @@
import java.util.*;
import com.oracle.graal.graph.*;
+import com.oracle.graal.graph.util.*;
import com.oracle.graal.nodes.*;
/**
@@ -37,22 +38,23 @@
*
* While iterating it maintains a user-defined state by calling the methods available in
* {@link MergeableState}.
- *
+ *
* @param the type of {@link MergeableState} handled by this PostOrderNodeIterator
*/
public abstract class PostOrderNodeIterator> {
private final NodeBitMap visitedEnds;
private final Deque nodeQueue;
- private final IdentityHashMap nodeStates;
+ private final Map nodeStates;
private final FixedNode start;
protected T state;
public PostOrderNodeIterator(FixedNode start, T initialState) {
- visitedEnds = start.graph().createNodeBitMap();
+ StructuredGraph graph = start.graph();
+ visitedEnds = graph.createNodeBitMap();
nodeQueue = new ArrayDeque<>();
- nodeStates = new IdentityHashMap<>();
+ nodeStates = CollectionsAccess.newNodeIdentityMap();
this.start = start;
this.state = initialState;
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java Mon May 12 21:29:29 2014 -0700
@@ -22,6 +22,8 @@
*/
package com.oracle.graal.phases.graph;
+import static com.oracle.graal.graph.util.CollectionsAccess.*;
+
import java.util.*;
import com.oracle.graal.compiler.common.cfg.*;
@@ -54,16 +56,16 @@
}
public static LoopInfo processLoop(BlockIteratorClosure closure, Loop loop, StateT initialState) {
- IdentityHashMap blockEndStates = apply(closure, loop.header, initialState, new HashSet<>(loop.blocks));
+ Map blockEndStates = apply(closure, loop.getHeader(), initialState, new HashSet<>(loop.getBlocks()));
LoopInfo info = new LoopInfo<>();
- List predecessors = loop.header.getPredecessors();
+ List predecessors = loop.getHeader().getPredecessors();
for (int i = 1; i < predecessors.size(); i++) {
StateT endState = blockEndStates.get(predecessors.get(i).getEndNode());
// make sure all end states are unique objects
info.endStates.add(closure.cloneState(endState));
}
- for (Block loopExit : loop.exits) {
+ for (Block loopExit : loop.getExits()) {
assert loopExit.getPredecessorCount() == 1;
assert blockEndStates.containsKey(loopExit.getBeginNode());
StateT exitState = blockEndStates.get(loopExit.getBeginNode());
@@ -77,12 +79,12 @@
apply(closure, start, closure.getInitialState(), null);
}
- public static IdentityHashMap apply(BlockIteratorClosure closure, Block start, StateT initialState, Set boundary) {
+ public static Map apply(BlockIteratorClosure closure, Block start, StateT initialState, Set boundary) {
Deque blockQueue = new ArrayDeque<>();
/*
* States are stored on EndNodes before merges, and on BeginNodes after ControlSplitNodes.
*/
- IdentityHashMap states = new IdentityHashMap<>();
+ Map states = newNodeIdentityMap();
StateT state = initialState;
Block current = start;
@@ -103,14 +105,14 @@
} else {
// recurse into the loop
Loop loop = successor.getLoop();
- LoopBeginNode loopBegin = (LoopBeginNode) loop.header.getBeginNode();
+ LoopBeginNode loopBegin = (LoopBeginNode) loop.getHeader().getBeginNode();
assert successor.getBeginNode() == loopBegin;
List exitStates = closure.processLoop(loop, state);
int i = 0;
- assert loop.exits.size() == exitStates.size();
- for (Block exit : loop.exits) {
+ assert loop.getExits().size() == exitStates.size();
+ for (Block exit : loop.getExits()) {
states.put(exit.getBeginNode(), exitStates.get(i++));
blockQueue.addFirst(exit);
}
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantNodeIterator.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantNodeIterator.java Mon May 12 20:17:25 2014 -0700
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantNodeIterator.java Mon May 12 21:29:29 2014 -0700
@@ -22,6 +22,8 @@
*/
package com.oracle.graal.phases.graph;
+import static com.oracle.graal.graph.util.CollectionsAccess.*;
+
import java.util.*;
import com.oracle.graal.graph.NodeClass.NodeClassIterator;
@@ -31,8 +33,8 @@
public static class LoopInfo {
- public final Map endStates = new IdentityHashMap<>(4);
- public final Map exitStates = new IdentityHashMap<>(2);
+ public final Map endStates = newNodeIdentityMap(4);
+ public final Map exitStates = newNodeIdentityMap(2);
}
public abstract static class NodeIteratorClosure {
@@ -76,13 +78,14 @@
return info;
}
- public static Map apply(NodeIteratorClosure closure, FixedNode start, StateT initialState) {
- return apply(closure, start, initialState, null);
+ public static void apply(NodeIteratorClosure closure, FixedNode start, StateT initialState) {
+ apply(closure, start, initialState, null);
}
private static Map apply(NodeIteratorClosure closure, FixedNode start, StateT initialState, LoopBeginNode boundary) {
+ assert start != null;
Deque nodeQueue = new ArrayDeque<>();
- IdentityHashMap blockEndStates = new IdentityHashMap<>();
+ Map blockEndStates = newNodeIdentityMap();
StateT state = initialState;
FixedNode current = start;
diff -r bb9473723904 -r 357e7202de5b graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/SinglePassNodeIterator.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/SinglePassNodeIterator.java Mon May 12 21:29:29 2014 -0700
@@ -0,0 +1,349 @@
+/*
+ * Copyright (c) 2011, 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.graal.phases.graph;
+
+import java.util.*;
+
+import com.oracle.graal.graph.*;
+import com.oracle.graal.graph.util.*;
+import com.oracle.graal.nodes.*;
+
+/**
+ * A SinglePassNodeIterator iterates the fixed nodes of the graph in post order starting from its
+ * start node. Unlike in iterative dataflow analysis, a single pass is performed, which allows
+ * keeping a smaller working set of pending {@link MergeableState}. This iteration scheme requires:
+ *
{@link #controlSplit(ControlSplitNode)} to always return all successors (otherwise, not all
+ * associated {@link EndNode} will be visited. In turn, visiting all the end nodes for a given
+ * {@link MergeNode} is a precondition before that merge node can be visited)
+ *
+ *
+ *
+ * For this iterator the CFG is defined by the classical CFG nodes (
+ * {@link com.oracle.graal.nodes.ControlSplitNode}, {@link com.oracle.graal.nodes.MergeNode}...) and
+ * the {@link com.oracle.graal.nodes.FixedWithNextNode#next() next} pointers of
+ * {@link com.oracle.graal.nodes.FixedWithNextNode}.
+ *
+ *
+ *
+ * The lifecycle that single-pass node iterators go through is described in {@link #apply()}
+ *
+ *
+ * @param the type of {@link MergeableState} handled by this SinglePassNodeIterator
+ */
+public abstract class SinglePassNodeIterator> {
+
+ private final NodeBitMap visitedEnds;
+
+ /**
+ * @see SinglePassNodeIterator.QElem
+ */
+ private final Deque> nodeQueue;
+
+ /**
+ * The keys in this map may be:
+ *
+ *
loop-begins and loop-ends, see {@link #finishLoopEnds(LoopEndNode)}
+ *
forward-ends of merge-nodes, see {@link #queueMerge(EndNode)}
+ *
+ *
+ *
+ * It's tricky to answer whether the state an entry contains is the pre-state or the post-state
+ * for the key in question, because states are mutable. Thus an entry may be created to contain
+ * a pre-state (at the time, as done for a loop-begin in {@link #apply()}) only to make it a
+ * post-state soon after (continuing with the loop-begin example, also in {@link #apply()}). In
+ * any case, given that keys are limited to the nodes mentioned in the previous paragraph, in
+ * all cases an entry can be considered to hold a post-state by the time such entry is
+ * retrieved.
+ *
+ *
+ *
+ * The only method that makes this map grow is {@link #keepForLater(FixedNode, MergeableState)}
+ * and the only one that shrinks it is {@link #pruneEntry(FixedNode)}. To make sure no entry is
+ * left behind inadvertently, asserts in {@link #finished()} are in place.
+ *
+ */
+ private final Map nodeStates;
+
+ private final StartNode start;
+
+ protected T state;
+
+ /**
+ * An item queued in {@link #nodeQueue} can be used to continue with the single-pass visit after
+ * the previous path can't be followed anymore. Such items are:
+ *
+ *
de-queued via {@link #nextQueuedNode()}
+ *
en-queued via {@link #queueMerge(EndNode)} and {@link #queueSuccessors(FixedNode)}
+ *
+ *
+ *
+ * Correspondingly each item may stand for:
+ *
+ *
a {@link MergeNode} whose pre-state results from merging those of its forward-ends, see
+ * {@link #nextQueuedNode()}
+ *
the successor of a control-split node, in which case the pre-state of the successor in
+ * question is also stored in the item, see {@link #nextQueuedNode()}
+ * After this method has been invoked, the {@link SinglePassNodeIterator} instance can't be used
+ * again. This saves clearing up fields in {@link #finished()}, the assumption being that this
+ * instance will be garbage-collected soon afterwards.
+ *
+ */
+ public void apply() {
+ FixedNode current = start;
+
+ do {
+ if (current instanceof InvokeWithExceptionNode) {
+ invoke((Invoke) current);
+ queueSuccessors(current);
+ current = nextQueuedNode();
+ } else if (current instanceof LoopBeginNode) {
+ state.loopBegin((LoopBeginNode) current);
+ keepForLater(current, state);
+ state = state.clone();
+ loopBegin((LoopBeginNode) current);
+ current = ((LoopBeginNode) current).next();
+ assert current != null;
+ } else if (current instanceof LoopEndNode) {
+ loopEnd((LoopEndNode) current);
+ finishLoopEnds((LoopEndNode) current);
+ current = nextQueuedNode();
+ } else if (current instanceof MergeNode) {
+ merge((MergeNode) current);
+ current = ((MergeNode) current).next();
+ assert current != null;
+ } else if (current instanceof FixedWithNextNode) {
+ FixedNode next = ((FixedWithNextNode) current).next();
+ assert next != null : current;
+ node(current);
+ current = next;
+ } else if (current instanceof EndNode) {
+ end((EndNode) current);
+ queueMerge((EndNode) current);
+ current = nextQueuedNode();
+ } else if (current instanceof ControlSinkNode) {
+ node(current);
+ current = nextQueuedNode();
+ } else if (current instanceof ControlSplitNode) {
+ controlSplit((ControlSplitNode) current);
+ queueSuccessors(current);
+ current = nextQueuedNode();
+ } else {
+ assert false : current;
+ }
+ } while (current != null);
+ finished();
+ }
+
+ private void queueSuccessors(FixedNode x) {
+ for (Node node : x.successors()) {
+ if (node != null) {
+ nodeQueue.addFirst(new QElem<>((BeginNode) node, state));
+ }
+ }
+ }
+
+ /**
+ * This method is invoked upon not having a (single) next {@link FixedNode} to visit. This
+ * method picks such next-node-to-visit from {@link #nodeQueue} and updates {@link #state} with
+ * the pre-state for that node.
+ *
+ *
+ * Upon reaching a {@link MergeNode}, some entries are pruned from {@link #nodeStates} (ie, the
+ * entries associated to forward-ends for that merge-node).
+ *
+ */
+ private FixedNode nextQueuedNode() {
+ if (nodeQueue.isEmpty()) {
+ return null;
+ }
+ QElem elem = nodeQueue.removeFirst();
+ if (elem.node instanceof MergeNode) {
+ MergeNode merge = (MergeNode) elem.node;
+ state = pruneEntry(merge.forwardEndAt(0)).clone();
+ ArrayList states = new ArrayList<>(merge.forwardEndCount() - 1);
+ for (int i = 1; i < merge.forwardEndCount(); i++) {
+ T other = pruneEntry(merge.forwardEndAt(i));
+ states.add(other);
+ }
+ boolean ready = state.merge(merge, states);
+ assert ready : "Not a single-pass iterator after all";
+ return merge;
+ } else {
+ BeginNode begin = (BeginNode) elem.node;
+ assert begin.predecessor() != null;
+ state = elem.preState.clone();
+ state.afterSplit(begin);
+ return begin;
+ }
+ }
+
+ /**
+ * Once all loop-end-nodes for a given loop-node have been visited:
+ *
+ *
the state for that loop-node is updated based on the states of the loop-end-nodes
+ *
entries in {@link #nodeStates} are pruned for the loop (they aren't going to be looked up
+ * again, anyway)
+ *
+ *
+ *
+ * The entries removed by this method were inserted:
+ *
+ *
for the loop-begin, by {@link #apply()}
+ *
for loop-ends, by (previous) invocations of this method
+ *
+ *
+ */
+ private void finishLoopEnds(LoopEndNode end) {
+ assert !visitedEnds.isMarked(end);
+ visitedEnds.mark(end);
+ keepForLater(end, state);
+ LoopBeginNode begin = end.loopBegin();
+ boolean endsVisited = true;
+ for (LoopEndNode le : begin.loopEnds()) {
+ if (!visitedEnds.isMarked(le)) {
+ endsVisited = false;
+ break;
+ }
+ }
+ if (endsVisited) {
+ ArrayList states = new ArrayList<>(begin.loopEnds().count());
+ for (LoopEndNode le : begin.orderedLoopEnds()) {
+ T leState = pruneEntry(le);
+ states.add(leState);
+ }
+ T loopBeginState = pruneEntry(begin);
+ loopBeginState.loopEnds(begin, states);
+ }
+ }
+
+ /**
+ * Once all end-nodes for a given merge-node have been visited, that merge-node is added to the
+ * {@link #nodeQueue}
+ *
+ *
+ * {@link #nextQueuedNode()} is in charge of pruning entries (held by {@link #nodeStates}) for
+ * the forward-ends inserted by this method.
+ *