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 double loopOrigFrequency;
47 protected int nextEndIndex;
48 protected int unswitches;
49 protected int splits;
50 protected int inversionCount;
51 protected LoopType loopType;
52 protected int unrollFactor;
53
54 public enum LoopType {
55 SIMPLE_LOOP,
56 PRE_LOOP,
57 MAIN_LOOP,
58 POST_LOOP
59 }
60
61 /** See {@link LoopEndNode#canSafepoint} for more information. */
62 boolean canEndsSafepoint;
63
64 @OptionalInput(InputType.Guard) GuardingNode overflowGuard;
65
66 public LoopBeginNode() {
67 super(TYPE);
68 loopFrequency = 1;
69 loopOrigFrequency = 1;
70 unswitches = 0;
71 splits = 0;
72 this.canEndsSafepoint = true;
73 loopType = LoopType.SIMPLE_LOOP;
74 unrollFactor = 1;
75 }
76
77 public boolean isSimpleLoop() {
78 return (loopType == LoopType.SIMPLE_LOOP);
79 }
80
81 public void setPreLoop() {
82 assert isSimpleLoop();
83 loopType = LoopType.PRE_LOOP;
84 }
85
86 public boolean isPreLoop() {
87 return (loopType == LoopType.PRE_LOOP);
88 }
89
90 public void setMainLoop() {
91 assert isSimpleLoop();
92 loopType = LoopType.MAIN_LOOP;
93 }
94
95 public boolean isMainLoop() {
96 return (loopType == LoopType.MAIN_LOOP);
97 }
98
99 public void setPostLoop() {
100 assert isSimpleLoop();
101 loopType = LoopType.POST_LOOP;
102 }
103
104 public boolean isPostLoop() {
105 return (loopType == LoopType.POST_LOOP);
106 }
107
108 public int getUnrollFactor() {
109 return unrollFactor;
110 }
111
112 public void setUnrollFactor(int currentUnrollFactor) {
113 unrollFactor = currentUnrollFactor;
114 }
115
116 /** Disables safepoint for the whole loop, i.e., for all {@link LoopEndNode loop ends}. */
117 public void disableSafepoint() {
118 /* Store flag locally in case new loop ends are created later on. */
119 this.canEndsSafepoint = false;
120 /* Propagate flag to all existing loop ends. */
121 for (LoopEndNode loopEnd : loopEnds()) {
122 loopEnd.disableSafepoint();
123 }
124 }
125
126 public double loopOrigFrequency() {
127 return loopOrigFrequency;
128 }
129
130 public void setLoopOrigFrequency(double loopOrigFrequency) {
131 assert loopOrigFrequency >= 0;
132 this.loopOrigFrequency = loopOrigFrequency;
133 }
134
135 public double loopFrequency() {
136 return loopFrequency;
137 }
138
139 public void setLoopFrequency(double loopFrequency) {
140 assert loopFrequency >= 0;
141 this.loopFrequency = loopFrequency;
142 }
143
144 /**
145 * Returns the <b>unordered</b> set of {@link LoopEndNode} that correspond to back-edges for
146 * this loop. The order of the back-edges is unspecified, if you need to get an ordering
147 * compatible for {@link PhiNode} creation, use {@link #orderedLoopEnds()}.
148 *
149 * @return the set of {@code LoopEndNode} that correspond to back-edges for this loop
150 */
151 public NodeIterable<LoopEndNode> loopEnds() {
152 return usages().filter(LoopEndNode.class);
153 }
154
155 public NodeIterable<LoopExitNode> loopExits() {
156 return usages().filter(LoopExitNode.class);
157 }
158
159 @Override
160 public NodeIterable<Node> anchored() {
161 return super.anchored().filter(isNotA(LoopEndNode.class).nor(LoopExitNode.class));
162 }
163
164 /**
165 * Returns the set of {@link LoopEndNode} that correspond to back-edges for this loop, in
166 * increasing {@link #phiPredecessorIndex} order. This method is suited to create new loop
167 * {@link PhiNode}.<br>
168 *
169 * For example a new PhiNode may be added as follow:
170 *
171 * <pre>
172 * PhiNode phi = new ValuePhiNode(stamp, loop);
173 * phi.addInput(forwardEdgeValue);
174 * for (LoopEndNode loopEnd : loop.orderedLoopEnds()) {
175 * phi.addInput(backEdgeValue(loopEnd));
176 * }
177 * </pre>
178 *
179 * @return the set of {@code LoopEndNode} that correspond to back-edges for this loop
180 */
181 public LoopEndNode[] orderedLoopEnds() {
182 LoopEndNode[] result = new LoopEndNode[this.getLoopEndCount()];
183 for (LoopEndNode end : loopEnds()) {
184 result[end.endIndex()] = end;
185 }
186 return result;
187 }
188
189 public boolean isSingleEntryLoop() {
190 return (forwardEndCount() == 1);
191 }
192
193 public AbstractEndNode forwardEnd() {
194 assert forwardEndCount() == 1;
195 return forwardEndAt(0);
196 }
197
198 public int splits() {
199 return splits;
200 }
201
202 public void incrementSplits() {
203 splits++;
204 }
205
206 @Override
207 public void generate(NodeLIRBuilderTool gen) {
208 // Nothing to emit, since this is node is used for structural purposes only.
209 }
210
211 @Override
212 protected void deleteEnd(AbstractEndNode end) {
213 if (end instanceof LoopEndNode) {
214 LoopEndNode loopEnd = (LoopEndNode) end;
215 loopEnd.setLoopBegin(null);
216 int idx = loopEnd.endIndex();
217 for (LoopEndNode le : loopEnds()) {
218 int leIdx = le.endIndex();
219 assert leIdx != idx;
220 if (leIdx > idx) {
221 le.setEndIndex(leIdx - 1);
222 }
223 }
224 nextEndIndex--;
225 } else {
226 super.deleteEnd(end);
227 }
228 }
229
230 @Override
231 public int phiPredecessorCount() {
232 return forwardEndCount() + loopEnds().count();
233 }
234
235 @Override
236 public int phiPredecessorIndex(AbstractEndNode pred) {
237 if (pred instanceof LoopEndNode) {
238 LoopEndNode loopEnd = (LoopEndNode) pred;
239 if (loopEnd.loopBegin() == this) {
240 assert loopEnd.endIndex() < loopEnds().count() : "Invalid endIndex : " + loopEnd;
241 return loopEnd.endIndex() + forwardEndCount();
242 }
243 } else {
244 return super.forwardEndIndex((EndNode) pred);
245 }
246 throw ValueNodeUtil.shouldNotReachHere("unknown pred : " + pred);
247 }
248
249 @Override
250 public AbstractEndNode phiPredecessorAt(int index) {
251 if (index < forwardEndCount()) {
252 return forwardEndAt(index);
253 }
254 for (LoopEndNode end : loopEnds()) {
255 int idx = index - forwardEndCount();
256 assert idx >= 0;
257 if (end.endIndex() == idx) {
258 return end;
259 }
260 }
261 throw ValueNodeUtil.shouldNotReachHere();
262 }
263
264 @Override
265 public boolean verify() {
266 assertTrue(loopEnds().isNotEmpty(), "missing loopEnd");
267 return super.verify();
268 }
269
270 int nextEndIndex() {
271 return nextEndIndex++;
272 }
273
274 public int getLoopEndCount() {
275 return nextEndIndex;
276 }
277
278 public int unswitches() {
279 return unswitches;
280 }
281
282 public void incrementUnswitches() {
283 unswitches++;
284 }
285
286 public int getInversionCount() {
287 return inversionCount;
288 }
289
290 public void setInversionCount(int count) {
291 inversionCount = count;
292 }
293
294 @Override
295 public void simplify(SimplifierTool tool) {
296 canonicalizePhis(tool);
297 }
298
299 public boolean isLoopExit(AbstractBeginNode begin) {
300 return begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == this;
301 }
302
303 public void removeExits() {
304 for (LoopExitNode loopexit : loopExits().snapshot()) {
305 loopexit.removeProxies();
306 FrameState loopStateAfter = loopexit.stateAfter();
307 graph().replaceFixedWithFixed(loopexit, graph().add(new BeginNode()));
308 if (loopStateAfter != null) {
309 GraphUtil.tryKillUnused(loopStateAfter);
310 }
311 }
312 }
313
314 public GuardingNode getOverflowGuard() {
315 return overflowGuard;
316 }
317
318 public void setOverflowGuard(GuardingNode overflowGuard) {
319 updateUsagesInterface(this.overflowGuard, overflowGuard);
320 this.overflowGuard = overflowGuard;
321 }
322
323 private static final int NO_INCREMENT = Integer.MIN_VALUE;
324
325 /**
326 * Returns an array with one entry for each input of the phi, which is either
327 * {@link #NO_INCREMENT} or the increment, i.e., the value by which the phi is incremented in
328 * the corresponding branch.
329 */
330 private static int[] getSelfIncrements(PhiNode phi) {
331 int[] selfIncrement = new int[phi.valueCount()];
332 for (int i = 0; i < phi.valueCount(); i++) {
333 ValueNode input = phi.valueAt(i);
334 long increment = NO_INCREMENT;
335 if (input != null && input instanceof AddNode && input.stamp() instanceof IntegerStamp) {
336 AddNode add = (AddNode) input;
337 if (add.getX() == phi && add.getY().isConstant()) {
338 increment = add.getY().asJavaConstant().asLong();
339 } else if (add.getY() == phi && add.getX().isConstant()) {
340 increment = add.getX().asJavaConstant().asLong();
341 }
342 } else if (input == phi) {
343 increment = 0;
344 }
345 if (increment < Integer.MIN_VALUE || increment > Integer.MAX_VALUE || increment == NO_INCREMENT) {
346 increment = NO_INCREMENT;
347 }
348 selfIncrement[i] = (int) increment;
349 }
350 return selfIncrement;
351 }
352
353 /**
354 * Coalesces loop phis that represent the same value (which is not handled by normal Global
355 * Value Numbering).
356 */
357 public void canonicalizePhis(SimplifierTool tool) {
358 int phiCount = phis().count();
359 if (phiCount > 1) {
360 int phiInputCount = phiPredecessorCount();
361 int phiIndex = 0;
362 int[][] selfIncrement = new int[phiCount][];
363 PhiNode[] phis = this.phis().snapshot().toArray(new PhiNode[phiCount]);
364
365 for (phiIndex = 0; phiIndex < phiCount; phiIndex++) {
366 PhiNode phi = phis[phiIndex];
367 if (phi != null) {
368 nextPhi: for (int otherPhiIndex = phiIndex + 1; otherPhiIndex < phiCount; otherPhiIndex++) {
369 PhiNode otherPhi = phis[otherPhiIndex];
370 if (otherPhi == null || phi.getNodeClass() != otherPhi.getNodeClass() || !phi.valueEquals(otherPhi)) {
371 continue nextPhi;
372 }
373 if (selfIncrement[phiIndex] == null) {
374 selfIncrement[phiIndex] = getSelfIncrements(phi);
375 }
376 if (selfIncrement[otherPhiIndex] == null) {
377 selfIncrement[otherPhiIndex] = getSelfIncrements(otherPhi);
378 }
379 int[] phiIncrement = selfIncrement[phiIndex];
380 int[] otherPhiIncrement = selfIncrement[otherPhiIndex];
381 for (int inputIndex = 0; inputIndex < phiInputCount; inputIndex++) {
382 if (phiIncrement[inputIndex] == NO_INCREMENT) {
383 if (phi.valueAt(inputIndex) != otherPhi.valueAt(inputIndex)) {
384 continue nextPhi;
385 }
386 }
387 if (phiIncrement[inputIndex] != otherPhiIncrement[inputIndex]) {
388 continue nextPhi;
389 }
390 }
391 if (tool != null) {
392 tool.addToWorkList(otherPhi.usages());
393 }
394 otherPhi.replaceAtUsages(phi);
395 GraphUtil.killWithUnusedFloatingInputs(otherPhi);
396 phis[otherPhiIndex] = null;
397 }
398 }
399 }
400 }
401 }
402 }