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  */
23 
24 
25 package org.graalvm.compiler.loop;
26 
27 import java.util.ArrayList;
28 import java.util.Collection;
29 import java.util.LinkedList;
30 import java.util.List;
31 
32 import jdk.internal.vm.compiler.collections.EconomicMap;
33 import jdk.internal.vm.compiler.collections.EconomicSet;
34 import jdk.internal.vm.compiler.collections.Equivalence;
35 import org.graalvm.compiler.core.common.cfg.Loop;
36 import org.graalvm.compiler.debug.DebugContext;
37 import org.graalvm.compiler.nodes.LoopBeginNode;
38 import org.graalvm.compiler.nodes.StructuredGraph;
39 import org.graalvm.compiler.nodes.ValueNode;
40 import org.graalvm.compiler.nodes.cfg.Block;
41 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
42 
43 public class LoopsData {
44     private final EconomicMap<LoopBeginNode, LoopEx> loopBeginToEx = EconomicMap.create(Equivalence.IDENTITY);
45     private final ControlFlowGraph cfg;
46     private final List<LoopEx> loops;
47 
48     @SuppressWarnings("try")
LoopsData(final StructuredGraph graph)49     public LoopsData(final StructuredGraph graph) {
50         DebugContext debug = graph.getDebug();
51         try (DebugContext.Scope s = debug.scope("ControlFlowGraph")) {
52             cfg = ControlFlowGraph.compute(graph, true, true, true, true);
53         } catch (Throwable e) {
54             throw debug.handle(e);
55         }
56         assert checkLoopOrder(cfg.getLoops());
57         loops = new ArrayList<>(cfg.getLoops().size());
58         for (Loop<Block> loop : cfg.getLoops()) {
59             LoopEx ex = new LoopEx(loop, this);
60             loops.add(ex);
61             loopBeginToEx.put(ex.loopBegin(), ex);
62         }
63     }
64 
65     /**
66      * Checks that loops are ordered such that outer loops appear first.
67      */
checkLoopOrder(Iterable<Loop<Block>> loops)68     private static boolean checkLoopOrder(Iterable<Loop<Block>> loops) {
69         EconomicSet<Loop<Block>> seen = EconomicSet.create(Equivalence.IDENTITY);
70         for (Loop<Block> loop : loops) {
71             if (loop.getParent() != null && !seen.contains(loop.getParent())) {
72                 return false;
73             }
74             seen.add(loop);
75         }
76         return true;
77     }
78 
loop(Loop<Block> loop)79     public LoopEx loop(Loop<Block> loop) {
80         return loopBeginToEx.get((LoopBeginNode) loop.getHeader().getBeginNode());
81     }
82 
loop(LoopBeginNode loopBegin)83     public LoopEx loop(LoopBeginNode loopBegin) {
84         return loopBeginToEx.get(loopBegin);
85     }
86 
loops()87     public List<LoopEx> loops() {
88         return loops;
89     }
90 
outerFirst()91     public List<LoopEx> outerFirst() {
92         return loops;
93     }
94 
countedLoops()95     public Collection<LoopEx> countedLoops() {
96         List<LoopEx> counted = new LinkedList<>();
97         for (LoopEx loop : loops()) {
98             if (loop.isCounted()) {
99                 counted.add(loop);
100             }
101         }
102         return counted;
103     }
104 
detectedCountedLoops()105     public void detectedCountedLoops() {
106         for (LoopEx loop : loops()) {
107             loop.detectCounted();
108         }
109     }
110 
getCFG()111     public ControlFlowGraph getCFG() {
112         return cfg;
113     }
114 
getInductionVariable(ValueNode value)115     public InductionVariable getInductionVariable(ValueNode value) {
116         InductionVariable match = null;
117         for (LoopEx loop : loops()) {
118             InductionVariable iv = loop.getInductionVariables().get(value);
119             if (iv != null) {
120                 if (match != null) {
121                     return null;
122                 }
123                 match = iv;
124             }
125         }
126         return match;
127     }
128 
129     /**
130      * Deletes any nodes created within the scope of this object that have no usages.
131      */
deleteUnusedNodes()132     public void deleteUnusedNodes() {
133         for (LoopEx loop : loops()) {
134             loop.deleteUnusedNodes();
135         }
136     }
137 }
138