1 /*
2 * Copyright (c) 2012, 2018, 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.Collection;
28 import java.util.LinkedList;
29 import java.util.Queue;
30
31 import jdk.internal.vm.compiler.collections.EconomicMap;
32 import jdk.internal.vm.compiler.collections.EconomicSet;
33 import jdk.internal.vm.compiler.collections.Equivalence;
34 import org.graalvm.compiler.core.common.calc.Condition;
35 import org.graalvm.compiler.core.common.cfg.Loop;
36 import org.graalvm.compiler.core.common.type.IntegerStamp;
37 import org.graalvm.compiler.debug.DebugContext;
38 import org.graalvm.compiler.debug.GraalError;
39 import org.graalvm.compiler.graph.Graph;
40 import org.graalvm.compiler.graph.Node;
41 import org.graalvm.compiler.graph.NodeBitMap;
42 import org.graalvm.compiler.graph.iterators.NodePredicate;
43 import org.graalvm.compiler.loop.InductionVariable.Direction;
44 import org.graalvm.compiler.nodes.AbstractBeginNode;
45 import org.graalvm.compiler.nodes.AbstractEndNode;
46 import org.graalvm.compiler.nodes.ConstantNode;
47 import org.graalvm.compiler.nodes.FixedGuardNode;
48 import org.graalvm.compiler.nodes.FixedNode;
49 import org.graalvm.compiler.nodes.FixedWithNextNode;
50 import org.graalvm.compiler.nodes.FrameState;
51 import org.graalvm.compiler.nodes.FullInfopointNode;
52 import org.graalvm.compiler.nodes.IfNode;
53 import org.graalvm.compiler.nodes.LogicNode;
54 import org.graalvm.compiler.nodes.LoopBeginNode;
55 import org.graalvm.compiler.nodes.NodeView;
56 import org.graalvm.compiler.nodes.PhiNode;
57 import org.graalvm.compiler.nodes.PiNode;
58 import org.graalvm.compiler.nodes.StructuredGraph;
59 import org.graalvm.compiler.nodes.ValueNode;
60 import org.graalvm.compiler.nodes.ValuePhiNode;
61 import org.graalvm.compiler.nodes.calc.AddNode;
62 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
63 import org.graalvm.compiler.nodes.calc.CompareNode;
64 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
65 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
66 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
67 import org.graalvm.compiler.nodes.calc.LeftShiftNode;
68 import org.graalvm.compiler.nodes.calc.MulNode;
69 import org.graalvm.compiler.nodes.calc.NegateNode;
70 import org.graalvm.compiler.nodes.calc.SignExtendNode;
71 import org.graalvm.compiler.nodes.calc.SubNode;
72 import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
73 import org.graalvm.compiler.nodes.cfg.Block;
74 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
75 import org.graalvm.compiler.nodes.debug.ControlFlowAnchored;
76 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
77 import org.graalvm.compiler.nodes.util.GraphUtil;
78
79 public class LoopEx {
80 private final Loop<Block> loop;
81 private LoopFragmentInside inside;
82 private LoopFragmentWhole whole;
83 private CountedLoopInfo counted;
84 private LoopsData data;
85 private EconomicMap<Node, InductionVariable> ivs;
86 private boolean countedLoopChecked;
87
88 LoopEx(Loop<Block> loop, LoopsData data) {
89 this.loop = loop;
90 this.data = data;
91 }
92
93 public Loop<Block> loop() {
94 return loop;
95 }
96
97 public LoopFragmentInside inside() {
98 if (inside == null) {
99 inside = new LoopFragmentInside(this);
100 }
101 return inside;
102 }
103
104 public LoopFragmentWhole whole() {
105 if (whole == null) {
106 whole = new LoopFragmentWhole(this);
107 }
108 return whole;
109 }
110
111 public void invalidateFragments() {
112 inside = null;
113 whole = null;
114 }
115
116 @SuppressWarnings("unused")
117 public LoopFragmentInsideFrom insideFrom(FixedNode point) {
118 // TODO (gd)
119 return null;
120 }
121
122 @SuppressWarnings("unused")
123 public LoopFragmentInsideBefore insideBefore(FixedNode point) {
124 // TODO (gd)
125 return null;
126 }
127
128 public boolean isOutsideLoop(Node n) {
129 return !whole().contains(n);
130 }
131
132 public LoopBeginNode loopBegin() {
133 return (LoopBeginNode) loop().getHeader().getBeginNode();
134 }
135
136 public FixedNode predecessor() {
137 return (FixedNode) loopBegin().forwardEnd().predecessor();
138 }
139
140 public FixedNode entryPoint() {
141 return loopBegin().forwardEnd();
142 }
143
144 public boolean isCounted() {
145 assert countedLoopChecked;
146 return counted != null;
147 }
148
149 public CountedLoopInfo counted() {
150 assert countedLoopChecked;
151 return counted;
152 }
153
154 public LoopEx parent() {
155 if (loop.getParent() == null) {
156 return null;
157 }
158 return data.loop(loop.getParent());
159 }
160
161 public int size() {
162 return whole().nodes().count();
163 }
164
165 @Override
166 public String toString() {
167 return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + loop().getDepth() + ") " + loopBegin();
168 }
169
170 private class InvariantPredicate implements NodePredicate {
171
172 private final Graph.Mark mark;
173
174 InvariantPredicate() {
175 this.mark = loopBegin().graph().getMark();
176 }
177
178 @Override
179 public boolean apply(Node n) {
180 if (loopBegin().graph().isNew(mark, n)) {
181 // Newly created nodes are unknown.
182 return false;
183 }
184 return isOutsideLoop(n);
185 }
186 }
187
188 public boolean reassociateInvariants() {
189 int count = 0;
190 StructuredGraph graph = loopBegin().graph();
191 InvariantPredicate invariant = new InvariantPredicate();
192 for (BinaryArithmeticNode<?> binary : whole().nodes().filter(BinaryArithmeticNode.class)) {
193 if (!binary.isAssociative()) {
194 continue;
195 }
196 ValueNode result = BinaryArithmeticNode.reassociate(binary, invariant, binary.getX(), binary.getY(), NodeView.DEFAULT);
197 if (result != binary) {
198 if (!result.isAlive()) {
199 assert !result.isDeleted();
200 result = graph.addOrUniqueWithInputs(result);
201 }
202 DebugContext debug = graph.getDebug();
203 if (debug.isLogEnabled()) {
204 debug.log("%s : Reassociated %s into %s", graph.method().format("%H::%n"), binary, result);
205 }
206 binary.replaceAtUsages(result);
207 GraphUtil.killWithUnusedFloatingInputs(binary);
208 count++;
209 }
210 }
211 return count != 0;
212 }
213
214 public boolean detectCounted() {
215 if (countedLoopChecked) {
216 return isCounted();
217 }
218 countedLoopChecked = true;
219 LoopBeginNode loopBegin = loopBegin();
220 FixedNode next = loopBegin.next();
221 while (next instanceof FixedGuardNode || next instanceof ValueAnchorNode || next instanceof FullInfopointNode) {
222 next = ((FixedWithNextNode) next).next();
223 }
224 if (next instanceof IfNode) {
225 IfNode ifNode = (IfNode) next;
226 boolean negated = false;
227 if (!isCfgLoopExit(ifNode.falseSuccessor())) {
228 if (!isCfgLoopExit(ifNode.trueSuccessor())) {
229 return false;
230 }
231 negated = true;
232 }
233 LogicNode ifTest = ifNode.condition();
234 if (!(ifTest instanceof IntegerLessThanNode) && !(ifTest instanceof IntegerEqualsNode)) {
235 if (ifTest instanceof IntegerBelowNode) {
236 ifTest.getDebug().log("Ignored potential Counted loop at %s with |<|", loopBegin);
237 }
238 return false;
239 }
240 CompareNode lessThan = (CompareNode) ifTest;
241 Condition condition = null;
242 InductionVariable iv = null;
243 ValueNode limit = null;
244 if (isOutsideLoop(lessThan.getX())) {
245 iv = getInductionVariables().get(lessThan.getY());
246 if (iv != null) {
247 condition = lessThan.condition().asCondition().mirror();
248 limit = lessThan.getX();
249 }
250 } else if (isOutsideLoop(lessThan.getY())) {
251 iv = getInductionVariables().get(lessThan.getX());
252 if (iv != null) {
253 condition = lessThan.condition().asCondition();
254 limit = lessThan.getY();
255 }
256 }
257 if (condition == null) {
258 return false;
259 }
260 if (negated) {
261 condition = condition.negate();
262 }
263 boolean oneOff = false;
264 switch (condition) {
265 case EQ:
266 return false;
267 case NE: {
268 if (!iv.isConstantStride() || Math.abs(iv.constantStride()) != 1) {
269 return false;
270 }
271 IntegerStamp initStamp = (IntegerStamp) iv.initNode().stamp(NodeView.DEFAULT);
272 IntegerStamp limitStamp = (IntegerStamp) limit.stamp(NodeView.DEFAULT);
273 if (iv.direction() == Direction.Up) {
274 if (initStamp.upperBound() > limitStamp.lowerBound()) {
275 return false;
276 }
277 } else if (iv.direction() == Direction.Down) {
278 if (initStamp.lowerBound() < limitStamp.upperBound()) {
279 return false;
280 }
281 } else {
282 return false;
283 }
284 break;
285 }
286 case LE:
287 oneOff = true;
288 if (iv.direction() != Direction.Up) {
289 return false;
290 }
291 break;
292 case LT:
293 if (iv.direction() != Direction.Up) {
294 return false;
295 }
296 break;
297 case GE:
298 oneOff = true;
299 if (iv.direction() != Direction.Down) {
300 return false;
301 }
302 break;
303 case GT:
304 if (iv.direction() != Direction.Down) {
305 return false;
306 }
307 break;
308 default:
309 throw GraalError.shouldNotReachHere(condition.toString());
310 }
311 counted = new CountedLoopInfo(this, iv, ifNode, limit, oneOff, negated ? ifNode.falseSuccessor() : ifNode.trueSuccessor());
312 return true;
313 }
314 return false;
315 }
316
317 private boolean isCfgLoopExit(AbstractBeginNode begin) {
318 Block block = data.getCFG().blockFor(begin);
319 return loop.getDepth() > block.getLoopDepth() || loop.isNaturalExit(block);
320 }
321
322 public LoopsData loopsData() {
323 return data;
324 }
325
326 public void nodesInLoopBranch(NodeBitMap branchNodes, AbstractBeginNode branch) {
327 EconomicSet<AbstractBeginNode> blocks = EconomicSet.create();
328 Collection<AbstractBeginNode> exits = new LinkedList<>();
329 Queue<Block> work = new LinkedList<>();
330 ControlFlowGraph cfg = loopsData().getCFG();
331 work.add(cfg.blockFor(branch));
332 while (!work.isEmpty()) {
333 Block b = work.remove();
334 if (loop().isLoopExit(b)) {
335 assert !exits.contains(b.getBeginNode());
336 exits.add(b.getBeginNode());
337 } else if (blocks.add(b.getBeginNode())) {
338 Block d = b.getDominatedSibling();
339 while (d != null) {
340 if (loop.getBlocks().contains(d)) {
341 work.add(d);
342 }
343 d = d.getDominatedSibling();
344 }
345 }
346 }
347 LoopFragment.computeNodes(branchNodes, branch.graph(), blocks, exits);
348 }
349
350 public EconomicMap<Node, InductionVariable> getInductionVariables() {
351 if (ivs == null) {
352 ivs = findInductionVariables(this);
353 }
354 return ivs;
355 }
356
357 /**
358 * Collect all the basic induction variables for the loop and the find any induction variables
359 * which are derived from the basic ones.
360 *
361 * @param loop
362 * @return a map from node to induction variable
363 */
364 private static EconomicMap<Node, InductionVariable> findInductionVariables(LoopEx loop) {
365 EconomicMap<Node, InductionVariable> ivs = EconomicMap.create(Equivalence.IDENTITY);
366
367 Queue<InductionVariable> scanQueue = new LinkedList<>();
368 LoopBeginNode loopBegin = loop.loopBegin();
369 AbstractEndNode forwardEnd = loopBegin.forwardEnd();
370 for (PhiNode phi : loopBegin.valuePhis()) {
371 ValueNode backValue = phi.singleBackValueOrThis();
372 if (backValue == phi) {
373 continue;
374 }
375 ValueNode stride = addSub(loop, backValue, phi);
376 if (stride != null) {
377 BasicInductionVariable biv = new BasicInductionVariable(loop, (ValuePhiNode) phi, phi.valueAt(forwardEnd), stride, (BinaryArithmeticNode<?>) backValue);
378 ivs.put(phi, biv);
379 scanQueue.add(biv);
380 }
381 }
382
383 while (!scanQueue.isEmpty()) {
384 InductionVariable baseIv = scanQueue.remove();
385 ValueNode baseIvNode = baseIv.valueNode();
386 for (ValueNode op : baseIvNode.usages().filter(ValueNode.class)) {
387 if (loop.isOutsideLoop(op)) {
388 continue;
389 }
390 if (op.usages().count() == 1 && op.usages().first() == baseIvNode) {
391 /*
392 * This is just the base induction variable increment with no other uses so
393 * don't bother reporting it.
394 */
395 continue;
396 }
397 InductionVariable iv = null;
398 ValueNode offset = addSub(loop, op, baseIvNode);
399 ValueNode scale;
400 if (offset != null) {
401 iv = new DerivedOffsetInductionVariable(loop, baseIv, offset, (BinaryArithmeticNode<?>) op);
402 } else if (op instanceof NegateNode) {
403 iv = new DerivedScaledInductionVariable(loop, baseIv, (NegateNode) op);
404 } else if ((scale = mul(loop, op, baseIvNode)) != null) {
405 iv = new DerivedScaledInductionVariable(loop, baseIv, scale, op);
406 } else {
407 boolean isValidConvert = op instanceof PiNode || op instanceof SignExtendNode;
408 if (!isValidConvert && op instanceof ZeroExtendNode) {
409 ZeroExtendNode zeroExtendNode = (ZeroExtendNode) op;
410 isValidConvert = zeroExtendNode.isInputAlwaysPositive() || ((IntegerStamp) zeroExtendNode.stamp(NodeView.DEFAULT)).isPositive();
411 }
412
413 if (isValidConvert) {
414 iv = new DerivedConvertedInductionVariable(loop, baseIv, op.stamp(NodeView.DEFAULT), op);
415 }
416 }
417
418 if (iv != null) {
419 ivs.put(op, iv);
420 scanQueue.offer(iv);
421 }
422 }
423 }
424 return ivs;
425 }
426
427 private static ValueNode addSub(LoopEx loop, ValueNode op, ValueNode base) {
428 if (op.stamp(NodeView.DEFAULT) instanceof IntegerStamp && (op instanceof AddNode || op instanceof SubNode)) {
429 BinaryArithmeticNode<?> aritOp = (BinaryArithmeticNode<?>) op;
430 if (aritOp.getX() == base && loop.isOutsideLoop(aritOp.getY())) {
431 return aritOp.getY();
432 } else if (aritOp.getY() == base && loop.isOutsideLoop(aritOp.getX())) {
433 return aritOp.getX();
434 }
435 }
436 return null;
437 }
438
439 private static ValueNode mul(LoopEx loop, ValueNode op, ValueNode base) {
440 if (op instanceof MulNode) {
441 MulNode mul = (MulNode) op;
442 if (mul.getX() == base && loop.isOutsideLoop(mul.getY())) {
443 return mul.getY();
444 } else if (mul.getY() == base && loop.isOutsideLoop(mul.getX())) {
445 return mul.getX();
446 }
447 }
448 if (op instanceof LeftShiftNode) {
449 LeftShiftNode shift = (LeftShiftNode) op;
450 if (shift.getX() == base && shift.getY().isConstant()) {
451 return ConstantNode.forIntegerStamp(base.stamp(NodeView.DEFAULT), 1 << shift.getY().asJavaConstant().asInt(), base.graph());
452 }
453 }
454 return null;
455 }
456
457 /**
458 * Deletes any nodes created within the scope of this object that have no usages.
459 */
460 public void deleteUnusedNodes() {
461 if (ivs != null) {
462 for (InductionVariable iv : ivs.getValues()) {
463 iv.deleteUnusedNodes();
464 }
465 }
466 }
467
468 /**
469 * @return true if all nodes in the loop can be duplicated.
470 */
471 public boolean canDuplicateLoop() {
472 for (Node node : inside().nodes()) {
473 if (node instanceof ControlFlowAnchored) {
474 return false;
475 }
476 if (node instanceof FrameState) {
477 FrameState frameState = (FrameState) node;
478 if (frameState.isExceptionHandlingBCI()) {
479 return false;
480 }
481 }
482 }
483 return true;
484 }
485 }