1 /*
2 * Copyright (c) 2011, 2015, 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 package org.graalvm.compiler.nodes;
24
25 import static org.graalvm.compiler.graph.iterators.NodePredicates.isNotA;
26
27 import org.graalvm.compiler.core.common.type.IntegerStamp;
28 import org.graalvm.compiler.graph.IterableNodeType;
29 import org.graalvm.compiler.graph.Node;
30 import org.graalvm.compiler.graph.NodeClass;
31 import org.graalvm.compiler.graph.iterators.NodeIterable;
32 import org.graalvm.compiler.graph.spi.SimplifierTool;
33 import org.graalvm.compiler.nodeinfo.InputType;
34 import org.graalvm.compiler.nodeinfo.NodeInfo;
35 import org.graalvm.compiler.nodes.calc.AddNode;
36 import org.graalvm.compiler.nodes.extended.GuardingNode;
37 import org.graalvm.compiler.nodes.spi.LIRLowerable;
38 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
39 import org.graalvm.compiler.nodes.util.GraphUtil;
40
41 @NodeInfo
42 public final class LoopBeginNode extends AbstractMergeNode implements IterableNodeType, LIRLowerable {
43
44 public static final NodeClass<LoopBeginNode> TYPE = NodeClass.create(LoopBeginNode.class);
45 protected double loopFrequency;
46 protected int nextEndIndex;
47 protected int unswitches;
48 protected int inversionCount;
49
50 /** See {@link LoopEndNode#canSafepoint} for more information. */
51 boolean canEndsSafepoint;
52
53 @OptionalInput(InputType.Guard) GuardingNode overflowGuard;
54
55 public LoopBeginNode() {
56 super(TYPE);
57 loopFrequency = 1;
58 this.canEndsSafepoint = true;
59 }
60
61 /** Disables safepoint for the whole loop, i.e., for all {@link LoopEndNode loop ends}. */
62 public void disableSafepoint() {
63 /* Store flag locally in case new loop ends are created later on. */
64 this.canEndsSafepoint = false;
65 /* Propagate flag to all existing loop ends. */
66 for (LoopEndNode loopEnd : loopEnds()) {
67 loopEnd.disableSafepoint();
68 }
69 }
70
71 public double loopFrequency() {
72 return loopFrequency;
73 }
74
75 public void setLoopFrequency(double loopFrequency) {
76 assert loopFrequency >= 0;
77 this.loopFrequency = loopFrequency;
78 }
79
80 /**
81 * Returns the <b>unordered</b> set of {@link LoopEndNode} that correspond to back-edges for
82 * this loop. The order of the back-edges is unspecified, if you need to get an ordering
83 * compatible for {@link PhiNode} creation, use {@link #orderedLoopEnds()}.
84 *
85 * @return the set of {@code LoopEndNode} that correspond to back-edges for this loop
86 */
87 public NodeIterable<LoopEndNode> loopEnds() {
88 return usages().filter(LoopEndNode.class);
89 }
90
91 public NodeIterable<LoopExitNode> loopExits() {
92 return usages().filter(LoopExitNode.class);
93 }
94
95 @Override
96 public NodeIterable<Node> anchored() {
97 return super.anchored().filter(isNotA(LoopEndNode.class).nor(LoopExitNode.class));
98 }
99
100 /**
101 * Returns the set of {@link LoopEndNode} that correspond to back-edges for this loop, in
102 * increasing {@link #phiPredecessorIndex} order. This method is suited to create new loop
103 * {@link PhiNode}.<br>
104 *
105 * For example a new PhiNode may be added as follow:
106 *
107 * <pre>
108 * PhiNode phi = new ValuePhiNode(stamp, loop);
109 * phi.addInput(forwardEdgeValue);
110 * for (LoopEndNode loopEnd : loop.orderedLoopEnds()) {
111 * phi.addInput(backEdgeValue(loopEnd));
112 * }
113 * </pre>
114 *
115 * @return the set of {@code LoopEndNode} that correspond to back-edges for this loop
116 */
117 public LoopEndNode[] orderedLoopEnds() {
118 LoopEndNode[] result = new LoopEndNode[this.getLoopEndCount()];
119 for (LoopEndNode end : loopEnds()) {
120 result[end.endIndex()] = end;
121 }
122 return result;
123 }
124
125 public AbstractEndNode forwardEnd() {
126 assert forwardEndCount() == 1;
127 return forwardEndAt(0);
128 }
129
130 @Override
131 public void generate(NodeLIRBuilderTool gen) {
132 // Nothing to emit, since this is node is used for structural purposes only.
133 }
134
135 @Override
136 protected void deleteEnd(AbstractEndNode end) {
137 if (end instanceof LoopEndNode) {
138 LoopEndNode loopEnd = (LoopEndNode) end;
139 loopEnd.setLoopBegin(null);
140 int idx = loopEnd.endIndex();
141 for (LoopEndNode le : loopEnds()) {
142 int leIdx = le.endIndex();
143 assert leIdx != idx;
144 if (leIdx > idx) {
145 le.setEndIndex(leIdx - 1);
146 }
147 }
148 nextEndIndex--;
149 } else {
150 super.deleteEnd(end);
151 }
152 }
153
154 @Override
155 public int phiPredecessorCount() {
156 return forwardEndCount() + loopEnds().count();
157 }
158
159 @Override
160 public int phiPredecessorIndex(AbstractEndNode pred) {
161 if (pred instanceof LoopEndNode) {
162 LoopEndNode loopEnd = (LoopEndNode) pred;
163 if (loopEnd.loopBegin() == this) {
164 assert loopEnd.endIndex() < loopEnds().count() : "Invalid endIndex : " + loopEnd;
165 return loopEnd.endIndex() + forwardEndCount();
166 }
167 } else {
168 return super.forwardEndIndex((EndNode) pred);
169 }
170 throw ValueNodeUtil.shouldNotReachHere("unknown pred : " + pred);
171 }
172
173 @Override
174 public AbstractEndNode phiPredecessorAt(int index) {
175 if (index < forwardEndCount()) {
176 return forwardEndAt(index);
177 }
178 for (LoopEndNode end : loopEnds()) {
179 int idx = index - forwardEndCount();
180 assert idx >= 0;
181 if (end.endIndex() == idx) {
182 return end;
183 }
184 }
185 throw ValueNodeUtil.shouldNotReachHere();
186 }
187
188 @Override
189 public boolean verify() {
190 assertTrue(loopEnds().isNotEmpty(), "missing loopEnd");
191 return super.verify();
192 }
193
194 int nextEndIndex() {
195 return nextEndIndex++;
196 }
197
198 public int getLoopEndCount() {
199 return nextEndIndex;
200 }
201
202 public int unswitches() {
203 return unswitches;
204 }
205
206 public void incrementUnswitches() {
207 unswitches++;
208 }
209
210 public int getInversionCount() {
211 return inversionCount;
212 }
213
214 public void setInversionCount(int count) {
215 inversionCount = count;
216 }
217
218 @Override
219 public void simplify(SimplifierTool tool) {
220 canonicalizePhis(tool);
221 }
222
223 public boolean isLoopExit(AbstractBeginNode begin) {
224 return begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == this;
225 }
226
227 public void removeExits() {
228 for (LoopExitNode loopexit : loopExits().snapshot()) {
229 loopexit.removeProxies();
230 FrameState loopStateAfter = loopexit.stateAfter();
231 graph().replaceFixedWithFixed(loopexit, graph().add(new BeginNode()));
232 if (loopStateAfter != null) {
233 GraphUtil.tryKillUnused(loopStateAfter);
234 }
235 }
236 }
237
238 public GuardingNode getOverflowGuard() {
239 return overflowGuard;
240 }
241
242 public void setOverflowGuard(GuardingNode overflowGuard) {
243 updateUsagesInterface(this.overflowGuard, overflowGuard);
244 this.overflowGuard = overflowGuard;
245 }
246
247 private static final int NO_INCREMENT = Integer.MIN_VALUE;
248
249 /**
250 * Returns an array with one entry for each input of the phi, which is either
251 * {@link #NO_INCREMENT} or the increment, i.e., the value by which the phi is incremented in
252 * the corresponding branch.
253 */
254 private static int[] getSelfIncrements(PhiNode phi) {
255 int[] selfIncrement = new int[phi.valueCount()];
256 for (int i = 0; i < phi.valueCount(); i++) {
257 ValueNode input = phi.valueAt(i);
258 long increment = NO_INCREMENT;
259 if (input != null && input instanceof AddNode && input.stamp() instanceof IntegerStamp) {
260 AddNode add = (AddNode) input;
261 if (add.getX() == phi && add.getY().isConstant()) {
262 increment = add.getY().asJavaConstant().asLong();
263 } else if (add.getY() == phi && add.getX().isConstant()) {
264 increment = add.getX().asJavaConstant().asLong();
265 }
266 } else if (input == phi) {
267 increment = 0;
268 }
269 if (increment < Integer.MIN_VALUE || increment > Integer.MAX_VALUE || increment == NO_INCREMENT) {
270 increment = NO_INCREMENT;
271 }
272 selfIncrement[i] = (int) increment;
273 }
274 return selfIncrement;
275 }
276
277 /**
278 * Coalesces loop phis that represent the same value (which is not handled by normal Global
279 * Value Numbering).
280 */
281 public void canonicalizePhis(SimplifierTool tool) {
282 int phiCount = phis().count();
283 if (phiCount > 1) {
284 int phiInputCount = phiPredecessorCount();
285 int phiIndex = 0;
286 int[][] selfIncrement = new int[phiCount][];
287 PhiNode[] phis = this.phis().snapshot().toArray(new PhiNode[phiCount]);
288
289 for (phiIndex = 0; phiIndex < phiCount; phiIndex++) {
290 PhiNode phi = phis[phiIndex];
291 if (phi != null) {
292 nextPhi: for (int otherPhiIndex = phiIndex + 1; otherPhiIndex < phiCount; otherPhiIndex++) {
293 PhiNode otherPhi = phis[otherPhiIndex];
294 if (otherPhi == null || phi.getNodeClass() != otherPhi.getNodeClass() || !phi.valueEquals(otherPhi)) {
295 continue nextPhi;
296 }
297 if (selfIncrement[phiIndex] == null) {
298 selfIncrement[phiIndex] = getSelfIncrements(phi);
299 }
300 if (selfIncrement[otherPhiIndex] == null) {
301 selfIncrement[otherPhiIndex] = getSelfIncrements(otherPhi);
302 }
303 int[] phiIncrement = selfIncrement[phiIndex];
304 int[] otherPhiIncrement = selfIncrement[otherPhiIndex];
305 for (int inputIndex = 0; inputIndex < phiInputCount; inputIndex++) {
306 if (phiIncrement[inputIndex] == NO_INCREMENT) {
307 if (phi.valueAt(inputIndex) != otherPhi.valueAt(inputIndex)) {
308 continue nextPhi;
309 }
310 }
311 if (phiIncrement[inputIndex] != otherPhiIncrement[inputIndex]) {
312 continue nextPhi;
313 }
314 }
315 if (tool != null) {
316 tool.addToWorkList(otherPhi.usages());
317 }
318 otherPhi.replaceAtUsages(phi);
319 GraphUtil.killWithUnusedFloatingInputs(otherPhi);
320 phis[otherPhiIndex] = null;
321 }
322 }
323 }
324 }
325 }
326 }