1 /*
2  * Copyright (c) 2012, 2020, 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.List;
29 
30 import jdk.internal.vm.compiler.collections.EconomicMap;
31 import jdk.internal.vm.compiler.collections.EconomicSet;
32 import jdk.internal.vm.compiler.collections.Equivalence;
33 import org.graalvm.compiler.core.common.cfg.Loop;
34 import org.graalvm.compiler.debug.DebugContext;
35 import org.graalvm.compiler.nodes.LoopBeginNode;
36 import org.graalvm.compiler.nodes.StructuredGraph;
37 import org.graalvm.compiler.nodes.ValueNode;
38 import org.graalvm.compiler.nodes.cfg.Block;
39 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
40 
41 public 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")
LoopsData(final StructuredGraph graph)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      */
checkLoopOrder(Iterable<Loop<Block>> loops)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 
loop(Loop<Block> loop)77     public LoopEx loop(Loop<Block> loop) {
78         return loopBeginToEx.get((LoopBeginNode) loop.getHeader().getBeginNode());
79     }
80 
loop(LoopBeginNode loopBegin)81     public LoopEx loop(LoopBeginNode loopBegin) {
82         return loopBeginToEx.get(loopBegin);
83     }
84 
loops()85     public List<LoopEx> loops() {
86         return loops;
87     }
88 
outerFirst()89     public List<LoopEx> outerFirst() {
90         return loops;
91     }
92 
countedLoops()93     public List<LoopEx> countedLoops() {
94         List<LoopEx> counted = new ArrayList<>();
95         for (LoopEx loop : loops()) {
96             if (loop.isCounted()) {
97                 counted.add(loop);
98             }
99         }
100         return counted;
101     }
102 
detectedCountedLoops()103     public void detectedCountedLoops() {
104         for (LoopEx loop : loops()) {
105             loop.detectCounted();
106         }
107     }
108 
getCFG()109     public ControlFlowGraph getCFG() {
110         return cfg;
111     }
112 
getInductionVariable(ValueNode value)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      */
deleteUnusedNodes()130     public void deleteUnusedNodes() {
131         for (LoopEx loop : loops()) {
132             loop.deleteUnusedNodes();
133         }
134     }
135 }
136