001/*
002 * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.graph;
024
025import static com.oracle.graal.graph.Graph.*;
026import static com.oracle.graal.graph.Node.*;
027import static jdk.internal.jvmci.common.UnsafeAccess.*;
028
029import java.util.*;
030import java.util.function.*;
031
032import com.oracle.graal.compiler.common.*;
033import com.oracle.graal.graph.NodeClass.EdgeInfo;
034
035/**
036 * Describes {@link Node} fields representing the set of inputs for the node or the set of the
037 * node's successors.
038 */
039public abstract class Edges extends Fields {
040
041    /**
042     * Constants denoting whether a set of edges are inputs or successors.
043     */
044    public enum Type {
045        Inputs,
046        Successors;
047    }
048
049    private final int directCount;
050    private final Type type;
051
052    public Edges(Type type, int directCount, ArrayList<? extends FieldsScanner.FieldInfo> edges) {
053        super(edges);
054        this.type = type;
055        this.directCount = directCount;
056    }
057
058    public static void translateInto(Edges edges, ArrayList<EdgeInfo> infos) {
059        for (int index = 0; index < edges.getCount(); index++) {
060            infos.add(new EdgeInfo(edges.offsets[index], edges.getName(index), edges.getType(index), edges.getDeclaringClass(index)));
061        }
062    }
063
064    private static Node getNodeUnsafe(Node node, long offset) {
065        return (Node) unsafe.getObject(node, offset);
066    }
067
068    @SuppressWarnings("unchecked")
069    private static NodeList<Node> getNodeListUnsafe(Node node, long offset) {
070        return (NodeList<Node>) unsafe.getObject(node, offset);
071    }
072
073    private static void putNodeUnsafe(Node node, long offset, Node value) {
074        unsafe.putObject(node, offset, value);
075    }
076
077    private static void putNodeListUnsafe(Node node, long offset, NodeList<?> value) {
078        unsafe.putObject(node, offset, value);
079    }
080
081    /**
082     * Get the number of direct edges represented by this object. A direct edge goes directly to
083     * another {@link Node}. An indirect edge goes via a {@link NodeList}.
084     */
085    public int getDirectCount() {
086        return directCount;
087    }
088
089    /**
090     * Gets the {@link Node} at the end point of a {@linkplain #getDirectCount() direct} edge.
091     *
092     * @param node one end point of the edge
093     * @param index the index of a non-list the edge (must be less than {@link #getDirectCount()})
094     * @return the Node at the other edge of the requested edge
095     */
096    public static Node getNode(Node node, long[] offsets, int index) {
097        return getNodeUnsafe(node, offsets[index]);
098    }
099
100    /**
101     * Gets the {@link NodeList} at the end point of a {@linkplain #getDirectCount() direct} edge.
102     *
103     * @param node one end point of the edge
104     * @param index the index of a non-list the edge (must be equal to or greater than
105     *            {@link #getDirectCount()})
106     * @return the {@link NodeList} at the other edge of the requested edge
107     */
108    public static NodeList<Node> getNodeList(Node node, long[] offsets, int index) {
109        return getNodeListUnsafe(node, offsets[index]);
110    }
111
112    /**
113     * Clear edges in a given node. This is accomplished by setting {@linkplain #getDirectCount()
114     * direct} edges to null and replacing the lists containing indirect edges with new lists. The
115     * latter is important so that this method can be used to clear the edges of cloned nodes.
116     *
117     * @param node the node whose edges are to be cleared
118     */
119    public void clear(Node node) {
120        final long[] curOffsets = this.offsets;
121        final Type curType = this.type;
122        int index = 0;
123        int curDirectCount = getDirectCount();
124        while (index < curDirectCount) {
125            initializeNode(node, curOffsets, index++, null);
126        }
127        int curCount = getCount();
128        while (index < curCount) {
129            NodeList<Node> list = getNodeList(node, curOffsets, index);
130            if (list != null) {
131                int size = list.initialSize;
132                NodeList<Node> newList = curType == Edges.Type.Inputs ? new NodeInputList<>(node, size) : new NodeSuccessorList<>(node, size);
133
134                // replacing with a new list object is the expected behavior!
135                initializeList(node, curOffsets, index, newList);
136            }
137            index++;
138        }
139    }
140
141    /**
142     * Initializes the list edges in a given node based on the size of the list edges in a prototype
143     * node.
144     *
145     * @param node the node whose list edges are to be initialized
146     * @param prototype the node whose list edge sizes are used when creating new edge lists
147     */
148    public void initializeLists(Node node, Node prototype) {
149        int index = getDirectCount();
150        final long[] curOffsets = this.offsets;
151        final Edges.Type curType = this.type;
152        while (index < getCount()) {
153            NodeList<Node> list = getNodeList(prototype, curOffsets, index);
154            if (list != null) {
155                int size = list.initialSize;
156                NodeList<Node> newList = curType == Edges.Type.Inputs ? new NodeInputList<>(node, size) : new NodeSuccessorList<>(node, size);
157                initializeList(node, curOffsets, index, newList);
158            }
159            index++;
160        }
161    }
162
163    /**
164     * Copies edges from {@code fromNode} to {@code toNode}. The nodes are expected to be of the
165     * exact same type.
166     *
167     * @param fromNode the node from which the edges should be copied.
168     * @param toNode the node to which the edges should be copied.
169     */
170    public void copy(Node fromNode, Node toNode) {
171        assert fromNode != toNode;
172        assert fromNode.getNodeClass().getClazz() == toNode.getNodeClass().getClazz();
173        int index = 0;
174        final long[] curOffsets = this.offsets;
175        final Type curType = this.type;
176        int curDirectCount = getDirectCount();
177        while (index < curDirectCount) {
178            initializeNode(toNode, curOffsets, index, getNode(fromNode, curOffsets, index));
179            index++;
180        }
181        int curCount = getCount();
182        while (index < curCount) {
183            NodeList<Node> list = getNodeList(toNode, curOffsets, index);
184            NodeList<Node> fromList = getNodeList(fromNode, curOffsets, index);
185            if (list == null || list == fromList) {
186                list = curType == Edges.Type.Inputs ? new NodeInputList<>(toNode, fromList) : new NodeSuccessorList<>(toNode, fromList);
187                initializeList(toNode, curOffsets, index, list);
188            } else {
189                list.copy(fromList);
190            }
191            index++;
192        }
193    }
194
195    /**
196     * Searches for the first edge in a given node matching {@code key} and if found, replaces it
197     * with {@code replacement}.
198     *
199     * @param node the node whose edges are to be searched
200     * @param key the edge to search for
201     * @param replacement the replacement for {@code key}
202     * @return true if a replacement was made
203     */
204    public boolean replaceFirst(Node node, Node key, Node replacement) {
205        int index = 0;
206        final long[] curOffsets = this.getOffsets();
207        int curDirectCount = getDirectCount();
208        while (index < curDirectCount) {
209            Node edge = getNode(node, curOffsets, index);
210            if (edge == key) {
211                assert replacement == null || getType(index).isAssignableFrom(replacement.getClass()) : "Can not assign " + replacement.getClass() + " to " + getType(index) + " in " + node;
212                initializeNode(node, curOffsets, index, replacement);
213                return true;
214            }
215            index++;
216        }
217        int curCount = getCount();
218        while (index < curCount) {
219            NodeList<Node> list = getNodeList(node, curOffsets, index);
220            if (list != null) {
221                if (list.replaceFirst(key, replacement)) {
222                    return true;
223                }
224            }
225            index++;
226        }
227        return false;
228    }
229
230    @Override
231    public void set(Object node, int index, Object value) {
232        throw new IllegalArgumentException("Cannot call set on " + this);
233    }
234
235    /**
236     * Sets the value of a given edge without notifying the new and old nodes on the other end of
237     * the edge of the change.
238     *
239     * @param node the node whose edge is to be updated
240     * @param index the index of the edge (between 0 and {@link #getCount()})
241     * @param value the node to be written to the edge
242     */
243    public static void initializeNode(Node node, long[] offsets, int index, Node value) {
244        putNodeUnsafe(node, offsets[index], value);
245    }
246
247    public static void initializeList(Node node, long[] offsets, int index, NodeList<Node> value) {
248        putNodeListUnsafe(node, offsets[index], value);
249    }
250
251    /**
252     * Sets the value of a given edge and notifies the new and old nodes on the other end of the
253     * edge of the change.
254     *
255     * @param node the node whose edge is to be updated
256     * @param index the index of the edge (between 0 and {@link #getCount()})
257     * @param value the node to be written to the edge
258     */
259    public void setNode(Node node, int index, Node value) {
260        assert index < directCount;
261        Node old = getNodeUnsafe(node, offsets[index]);
262        putNodeUnsafe(node, offsets[index], value);
263        update(node, old, value);
264    }
265
266    public abstract void update(Node node, Node oldValue, Node newValue);
267
268    public boolean contains(Node node, Node value) {
269        final long[] curOffsets = this.offsets;
270        for (int i = 0; i < directCount; i++) {
271            if (getNode(node, curOffsets, i) == value) {
272                return true;
273            }
274        }
275        for (int i = directCount; i < getCount(); i++) {
276            NodeList<?> curList = getNodeList(node, curOffsets, i);
277            if (curList != null && curList.contains(value)) {
278                return true;
279            }
280        }
281        return false;
282    }
283
284    /**
285     * Determines if the edges of two given nodes are the same.
286     */
287    public boolean areEqualIn(Node node, Node other) {
288        assert node.getNodeClass().getClazz() == other.getNodeClass().getClazz();
289        int index = 0;
290        final long[] curOffsets = this.offsets;
291        while (index < directCount) {
292            if (getNode(other, curOffsets, index) != getNode(node, curOffsets, index)) {
293                return false;
294            }
295            index++;
296        }
297        while (index < getCount()) {
298            NodeList<Node> list = getNodeList(other, curOffsets, index);
299            if (!Objects.equals(list, getNodeList(node, curOffsets, index))) {
300                return false;
301            }
302            index++;
303        }
304        return true;
305    }
306
307    /**
308     * An iterator that will iterate over edges.
309     *
310     * An iterator of this type will not return null values, unless edges are modified concurrently.
311     * Concurrent modifications are detected by an assertion on a best-effort basis.
312     */
313    private static class EdgesIterator implements NodePosIterator {
314        protected final Node node;
315        protected final Edges edges;
316        protected int index;
317        protected int subIndex;
318        NodeList<Node> list;
319        protected boolean needsForward;
320        protected Node nextElement;
321        protected final int directCount;
322        protected final int count;
323        protected final long[] offsets;
324
325        /**
326         * Creates an iterator that will iterate over some given edges in a given node.
327         */
328        EdgesIterator(Node node, Edges edges) {
329            this.node = node;
330            this.edges = edges;
331            index = NOT_ITERABLE;
332            subIndex = 0;
333            needsForward = true;
334            this.directCount = edges.getDirectCount();
335            this.offsets = edges.getOffsets();
336            this.count = edges.getCount();
337        }
338
339        void forward() {
340            needsForward = false;
341            if (index < directCount) {
342                index++;
343                while (index < directCount) {
344                    nextElement = Edges.getNode(node, offsets, index);
345                    if (nextElement != null) {
346                        return;
347                    }
348                    index++;
349                }
350            } else {
351                subIndex++;
352            }
353            if (index < edges.getCount()) {
354                forwardNodeList();
355            }
356        }
357
358        private void forwardNodeList() {
359            do {
360                if (subIndex == 0) {
361                    list = Edges.getNodeList(node, offsets, index);
362                }
363                if (list != null) {
364                    while (subIndex < list.size()) {
365                        nextElement = list.get(subIndex);
366                        if (nextElement != null) {
367                            return;
368                        }
369                        subIndex++;
370                    }
371                }
372                subIndex = 0;
373                index++;
374            } while (index < edges.getCount());
375        }
376
377        private Node nextElement() {
378            if (needsForward) {
379                forward();
380            }
381            needsForward = true;
382            if (index < count) {
383                return nextElement;
384            }
385            throw new NoSuchElementException();
386        }
387
388        @Override
389        public boolean hasNext() {
390            if (needsForward) {
391                forward();
392            }
393            return index < edges.getCount();
394        }
395
396        @Override
397        public Node next() {
398            return nextElement();
399        }
400
401        public Position nextPosition() {
402            if (needsForward) {
403                forward();
404            }
405            needsForward = true;
406            if (index < directCount) {
407                return new Position(edges, index, NOT_ITERABLE);
408            } else {
409                return new Position(edges, index, subIndex);
410            }
411        }
412
413        @Override
414        public void remove() {
415            throw new UnsupportedOperationException();
416        }
417    }
418
419    private static class AllEdgesIterator extends EdgesIterator {
420
421        AllEdgesIterator(Node node, Edges edges) {
422            super(node, edges);
423        }
424
425        @Override
426        void forward() {
427            needsForward = false;
428            if (index < directCount) {
429                index++;
430                if (index < edges.getDirectCount()) {
431                    nextElement = Edges.getNode(node, edges.getOffsets(), index);
432                    return;
433                }
434            } else {
435                subIndex++;
436            }
437            while (index < edges.getCount()) {
438                if (subIndex == 0) {
439                    list = Edges.getNodeList(node, edges.getOffsets(), index);
440                }
441                if (list != null) {
442                    if (subIndex < list.size()) {
443                        nextElement = list.get(subIndex);
444                        return;
445                    }
446                }
447                subIndex = 0;
448                index++;
449            }
450        }
451    }
452
453    private static final class EdgesWithModCountIterator extends EdgesIterator {
454        private final int modCount;
455
456        private EdgesWithModCountIterator(Node node, Edges edges) {
457            super(node, edges);
458            assert MODIFICATION_COUNTS_ENABLED;
459            this.modCount = node.modCount();
460        }
461
462        @Override
463        public boolean hasNext() {
464            try {
465                return super.hasNext();
466            } finally {
467                assert modCount == node.modCount() : "must not be modified";
468            }
469        }
470
471        @Override
472        public Node next() {
473            try {
474                return super.next();
475            } finally {
476                assert modCount == node.modCount() : "must not be modified";
477            }
478        }
479
480        @Override
481        public Position nextPosition() {
482            try {
483                return super.nextPosition();
484            } finally {
485                assert modCount == node.modCount();
486            }
487        }
488    }
489
490    static int cnt1;
491    static int cnt2;
492
493    public NodeClassIterable getIterable(final Node node) {
494        return new NodeClassIterable() {
495
496            @Override
497            public EdgesIterator iterator() {
498                if (MODIFICATION_COUNTS_ENABLED) {
499                    return new EdgesWithModCountIterator(node, Edges.this);
500                } else {
501                    return new EdgesIterator(node, Edges.this);
502                }
503            }
504
505            public EdgesIterator withNullIterator() {
506                return new AllEdgesIterator(node, Edges.this);
507            }
508
509            @Override
510            public boolean contains(Node other) {
511                return Edges.this.contains(node, other);
512            }
513        };
514    }
515
516    public Type type() {
517        return type;
518    }
519
520    public void accept(Node node, BiConsumer<Node, Node> consumer) {
521        int index = 0;
522        int curDirectCount = this.directCount;
523        final long[] curOffsets = this.offsets;
524        while (index < curDirectCount) {
525            Node curNode = getNode(node, curOffsets, index);
526            if (curNode != null) {
527                consumer.accept(node, curNode);
528            }
529            index++;
530        }
531        int count = curOffsets.length;
532        while (index < count) {
533            NodeList<Node> list = getNodeList(node, curOffsets, index);
534            acceptHelper(node, consumer, list);
535            index++;
536        }
537    }
538
539    private static void acceptHelper(Node node, BiConsumer<Node, Node> consumer, NodeList<Node> list) {
540        if (list != null) {
541            for (int i = 0; i < list.size(); ++i) {
542                Node curNode = list.get(i);
543                if (curNode != null) {
544                    consumer.accept(node, curNode);
545                }
546            }
547        }
548    }
549
550    public void pushAll(Node node, NodeStack stack) {
551        int index = 0;
552        int curDirectCount = this.directCount;
553        final long[] curOffsets = this.offsets;
554        while (index < curDirectCount) {
555            Node curNode = getNode(node, curOffsets, index);
556            if (curNode != null) {
557                stack.push(curNode);
558            }
559            index++;
560        }
561        int count = curOffsets.length;
562        while (index < count) {
563            NodeList<Node> list = getNodeList(node, curOffsets, index);
564            pushAllHelper(stack, list);
565            index++;
566        }
567    }
568
569    private static void pushAllHelper(NodeStack stack, NodeList<Node> list) {
570        if (list != null) {
571            for (int i = 0; i < list.size(); ++i) {
572                Node curNode = list.get(i);
573                if (curNode != null) {
574                    stack.push(curNode);
575                }
576            }
577        }
578    }
579}