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