LoopsData.java revision 13264:48566d838608 
1/*
2 * Copyright (c) 2012, 2017, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23package org.graalvm.compiler.loop;
24
25import java.util.ArrayList;
26import java.util.Collection;
27import java.util.LinkedList;
28import java.util.List;
29
30import org.graalvm.compiler.core.common.cfg.Loop;
31import org.graalvm.compiler.debug.DebugContext;
32import org.graalvm.compiler.nodes.LoopBeginNode;
33import org.graalvm.compiler.nodes.StructuredGraph;
34import org.graalvm.compiler.nodes.ValueNode;
35import org.graalvm.compiler.nodes.cfg.Block;
36import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
37import org.graalvm.util.EconomicMap;
38import org.graalvm.util.EconomicSet;
39import org.graalvm.util.Equivalence;
40
41public class LoopsData {
42    private final EconomicMap<LoopBeginNode, LoopEx> loopBeginToEx = EconomicMap.create(Equivalence.IDENTITY);
43    private final ControlFlowGraph cfg;
44    private final List<LoopEx> loops;
45
46    @SuppressWarnings("try")
47    public LoopsData(final StructuredGraph graph) {
48        DebugContext debug = graph.getDebug();
49        try (DebugContext.Scope s = debug.scope("ControlFlowGraph")) {
50            cfg = ControlFlowGraph.compute(graph, true, true, true, true);
51        } catch (Throwable e) {
52            throw debug.handle(e);
53        }
54        assert checkLoopOrder(cfg.getLoops());
55        loops = new ArrayList<>(cfg.getLoops().size());
56        for (Loop<Block> loop : cfg.getLoops()) {
57            LoopEx ex = new LoopEx(loop, this);
58            loops.add(ex);
59            loopBeginToEx.put(ex.loopBegin(), ex);
60        }
61    }
62
63    /**
64     * Checks that loops are ordered such that outer loops appear first.
65     */
66    private static boolean checkLoopOrder(Iterable<Loop<Block>> loops) {
67        EconomicSet<Loop<Block>> seen = EconomicSet.create(Equivalence.IDENTITY);
68        for (Loop<Block> loop : loops) {
69            if (loop.getParent() != null && !seen.contains(loop.getParent())) {
70                return false;
71            }
72            seen.add(loop);
73        }
74        return true;
75    }
76
77    public LoopEx loop(Loop<Block> loop) {
78        return loopBeginToEx.get((LoopBeginNode) loop.getHeader().getBeginNode());
79    }
80
81    public LoopEx loop(LoopBeginNode loopBegin) {
82        return loopBeginToEx.get(loopBegin);
83    }
84
85    public List<LoopEx> loops() {
86        return loops;
87    }
88
89    public List<LoopEx> outerFirst() {
90        return loops;
91    }
92
93    public Collection<LoopEx> countedLoops() {
94        List<LoopEx> counted = new LinkedList<>();
95        for (LoopEx loop : loops()) {
96            if (loop.isCounted()) {
97                counted.add(loop);
98            }
99        }
100        return counted;
101    }
102
103    public void detectedCountedLoops() {
104        for (LoopEx loop : loops()) {
105            loop.detectCounted();
106        }
107    }
108
109    public ControlFlowGraph getCFG() {
110        return cfg;
111    }
112
113    public InductionVariable getInductionVariable(ValueNode value) {
114        InductionVariable match = null;
115        for (LoopEx loop : loops()) {
116            InductionVariable iv = loop.getInductionVariables().get(value);
117            if (iv != null) {
118                if (match != null) {
119                    return null;
120                }
121                match = iv;
122            }
123        }
124        return match;
125    }
126
127    /**
128     * Deletes any nodes created within the scope of this object that have no usages.
129     */
130    public void deleteUnusedNodes() {
131        for (LoopEx loop : loops()) {
132            loop.deleteUnusedNodes();
133        }
134    }
135}
136