# HG changeset patch # User Doug Simon # Date 1423750814 -3600 # Node ID 49605c649beb474e6855c98ed45eb763cab7f88e # Parent 5664cadb3cee9bf396fde953a1696aca5c11b0df# Parent de5ef2d5498f28d05cab68aff93ebef542672413 Merge. diff -r 5664cadb3cee -r 49605c649beb graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUnionFind.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUnionFind.java Thu Feb 12 15:20:14 2015 +0100 @@ -0,0 +1,94 @@ +/* + * Copyright (c) 2015, 2015, 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.graph; + +/** + * Union-find data structure for {@link Node Nodes}. + * + * All operations have an accumulated worst-case complexity of O(a(n)), where a(n) is the inverse of + * the Ackermann function A(n,n). + */ +public class NodeUnionFind extends NodeIdAccessor { + + private int[] rank; + private int[] parent; + + /** + * Create a new union-find data structure for a {@link Graph}. Initially, all nodes are in their + * own equivalence set. + */ + public NodeUnionFind(Graph graph) { + super(graph); + rank = new int[graph.nodeIdCount()]; + parent = new int[graph.nodeIdCount()]; + for (int i = 0; i < parent.length; i++) { + parent[i] = i; + } + } + + /** + * Merge the equivalence sets of two nodes. + * + * After calling this function, find(a) == find(b). + */ + public void union(Node a, Node b) { + union(getNodeId(a), getNodeId(b)); + } + + /** + * Get a representative element of the equivalence set of a node. + * + * This function returns the same representative element for all members of the same equivalence + * set, i.e., find(a) == find(b) if and only if a and b are in the same set. + */ + public Node find(Node a) { + int id = find(getNodeId(a)); + return graph.getNode(id); + } + + public boolean equiv(Node a, Node b) { + return find(getNodeId(a)) == find(getNodeId(b)); + } + + private void union(int a, int b) { + int aRoot = find(a); + int bRoot = find(b); + if (rank[aRoot] < rank[bRoot]) { + parent[aRoot] = bRoot; + } else { + parent[bRoot] = aRoot; + if (rank[aRoot] == rank[bRoot]) { + rank[aRoot]++; + } + } + } + + private int find(int a) { + int ret = a; + while (ret != parent[ret]) { + parent[ret] = parent[parent[ret]]; + ret = parent[ret]; + } + return ret; + } +} diff -r 5664cadb3cee -r 49605c649beb graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/FrameWithoutBoxing.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/FrameWithoutBoxing.java Thu Feb 12 12:00:20 2015 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/FrameWithoutBoxing.java Thu Feb 12 15:20:14 2015 +0100 @@ -243,26 +243,24 @@ private void verifySet(FrameSlot slot, FrameSlotKind accessKind) { int slotIndex = slot.getIndex(); - byte[] tagsArray = getTags(); - if (slotIndex >= tagsArray.length) { + if (slotIndex >= getTags().length) { CompilerDirectives.transferToInterpreter(); if (!resize()) { throw new IllegalArgumentException(String.format("The frame slot '%s' is not known by the frame descriptor.", slot)); } } - tagsArray[slotIndex] = (byte) accessKind.ordinal(); + getTags()[slotIndex] = (byte) accessKind.ordinal(); } private void verifyGet(FrameSlot slot, FrameSlotKind accessKind) throws FrameSlotTypeException { int slotIndex = slot.getIndex(); - byte[] tagsArray = getTags(); - if (slotIndex >= tagsArray.length) { + if (slotIndex >= getTags().length) { CompilerDirectives.transferToInterpreter(); if (!resize()) { throw new IllegalArgumentException(String.format("The frame slot '%s' is not known by the frame descriptor.", slot)); } } - byte tag = tagsArray[slotIndex]; + byte tag = this.getTags()[slotIndex]; if (tag != accessKind.ordinal()) { CompilerDirectives.transferToInterpreter(); throw new FrameSlotTypeException(); diff -r 5664cadb3cee -r 49605c649beb graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/expression/DSLExpressionResolver.java --- a/graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/expression/DSLExpressionResolver.java Thu Feb 12 12:00:20 2015 +0100 +++ b/graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/expression/DSLExpressionResolver.java Thu Feb 12 15:20:14 2015 +0100 @@ -60,7 +60,7 @@ public DSLExpressionResolver copy(List prefixElements) { DSLExpressionResolver resolver = new DSLExpressionResolver(context); - lookup(prefixElements); + resolver.lookup(prefixElements); resolver.variables.addAll(variables); resolver.methods.addAll(methods); return resolver; diff -r 5664cadb3cee -r 49605c649beb graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/java/ElementUtils.java --- a/graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/java/ElementUtils.java Thu Feb 12 12:00:20 2015 +0100 +++ b/graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/java/ElementUtils.java Thu Feb 12 15:20:14 2015 +0100 @@ -569,7 +569,7 @@ public static TypeElement findNearestEnclosingType(Element element) { List elements = getElementHierarchy(element); for (Element e : elements) { - if (e.getKind().isClass()) { + if (e.getKind().isClass() || e.getKind().isInterface()) { return (TypeElement) e; } }