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.loop;
24
25 import static org.graalvm.compiler.graph.Node.newIdentityMap;
26
27 import java.util.Collection;
28 import java.util.Collections;
29 import java.util.LinkedList;
30 import java.util.Map;
31 import java.util.Queue;
32
33 import org.graalvm.compiler.core.common.calc.Condition;
34 import org.graalvm.compiler.core.common.cfg.Loop;
35 import org.graalvm.compiler.core.common.type.IntegerStamp;
36 import org.graalvm.compiler.debug.Debug;
37 import org.graalvm.compiler.debug.GraalError;
38 import org.graalvm.compiler.graph.Node;
39 import org.graalvm.compiler.graph.NodeBitMap;
40 import org.graalvm.compiler.graph.iterators.NodePredicate;
41 import org.graalvm.compiler.loop.InductionVariable.Direction;
42 import org.graalvm.compiler.nodes.AbstractBeginNode;
43 import org.graalvm.compiler.nodes.AbstractEndNode;
44 import org.graalvm.compiler.nodes.ConstantNode;
45 import org.graalvm.compiler.nodes.FixedGuardNode;
46 import org.graalvm.compiler.nodes.FixedNode;
47 import org.graalvm.compiler.nodes.FixedWithNextNode;
48 import org.graalvm.compiler.nodes.FrameState;
49 import org.graalvm.compiler.nodes.FullInfopointNode;
50 import org.graalvm.compiler.nodes.IfNode;
53 import org.graalvm.compiler.nodes.LoopExitNode;
54 import org.graalvm.compiler.nodes.PhiNode;
55 import org.graalvm.compiler.nodes.PiNode;
56 import org.graalvm.compiler.nodes.StructuredGraph;
57 import org.graalvm.compiler.nodes.ValueNode;
58 import org.graalvm.compiler.nodes.ValuePhiNode;
59 import org.graalvm.compiler.nodes.calc.AddNode;
60 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
61 import org.graalvm.compiler.nodes.calc.CompareNode;
62 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
63 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
64 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
65 import org.graalvm.compiler.nodes.calc.LeftShiftNode;
66 import org.graalvm.compiler.nodes.calc.MulNode;
67 import org.graalvm.compiler.nodes.calc.NegateNode;
68 import org.graalvm.compiler.nodes.calc.SignExtendNode;
69 import org.graalvm.compiler.nodes.calc.SubNode;
70 import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
71 import org.graalvm.compiler.nodes.cfg.Block;
72 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
73 import org.graalvm.compiler.nodes.debug.ControlFlowAnchorNode;
74 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
75 import org.graalvm.compiler.nodes.util.GraphUtil;
76
77 import jdk.vm.ci.code.BytecodeFrame;
78
79 public class LoopEx {
80
81 private final Loop<Block> loop;
82 private LoopFragmentInside inside;
83 private LoopFragmentWhole whole;
84 private CountedLoopInfo counted;
85 private LoopsData data;
86 private Map<Node, InductionVariable> ivs;
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);
163 @Override
164 public String toString() {
165 return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + loop().getDepth() + ") " + loopBegin();
166 }
167
168 private class InvariantPredicate implements NodePredicate {
169
170 @Override
171 public boolean apply(Node n) {
172 return isOutsideLoop(n);
173 }
174 }
175
176 public void reassociateInvariants() {
177 InvariantPredicate invariant = new InvariantPredicate();
178 StructuredGraph graph = loopBegin().graph();
179 for (BinaryArithmeticNode<?> binary : whole().nodes().filter(BinaryArithmeticNode.class)) {
180 if (!binary.isAssociative()) {
181 continue;
182 }
183 BinaryArithmeticNode<?> result = BinaryArithmeticNode.reassociate(binary, invariant, binary.getX(), binary.getY());
184 if (result != binary) {
185 if (Debug.isLogEnabled()) {
186 Debug.log("%s : Reassociated %s into %s", graph.method().format("%H::%n"), binary, result);
187 }
188 if (!result.isAlive()) {
189 assert !result.isDeleted();
190 result = graph.addOrUniqueWithInputs(result);
191 }
192 binary.replaceAtUsages(result);
193 GraphUtil.killWithUnusedFloatingInputs(binary);
194 }
195 }
196 }
197
198 public boolean detectCounted() {
199 LoopBeginNode loopBegin = loopBegin();
200 FixedNode next = loopBegin.next();
201 while (next instanceof FixedGuardNode || next instanceof ValueAnchorNode || next instanceof FullInfopointNode) {
202 next = ((FixedWithNextNode) next).next();
203 }
293 }
294 return false;
295 }
296
297 public LoopsData loopsData() {
298 return data;
299 }
300
301 public void nodesInLoopBranch(NodeBitMap branchNodes, AbstractBeginNode branch) {
302 Collection<AbstractBeginNode> blocks = new LinkedList<>();
303 Collection<LoopExitNode> exits = new LinkedList<>();
304 Queue<Block> work = new LinkedList<>();
305 ControlFlowGraph cfg = loopsData().getCFG();
306 work.add(cfg.blockFor(branch));
307 while (!work.isEmpty()) {
308 Block b = work.remove();
309 if (loop().getExits().contains(b)) {
310 exits.add((LoopExitNode) b.getBeginNode());
311 } else {
312 blocks.add(b.getBeginNode());
313 for (Block d : b.getDominated()) {
314 if (loop.getBlocks().contains(d)) {
315 work.add(d);
316 }
317 }
318 }
319 }
320 LoopFragment.computeNodes(branchNodes, branch.graph(), blocks, exits);
321 }
322
323 public Map<Node, InductionVariable> getInductionVariables() {
324 if (ivs == null) {
325 ivs = findInductionVariables(this);
326 }
327 return ivs;
328 }
329
330 /**
331 * Collect all the basic induction variables for the loop and the find any induction variables
332 * which are derived from the basic ones.
333 *
334 * @param loop
335 * @return a map from node to induction variable
336 */
337 private static Map<Node, InductionVariable> findInductionVariables(LoopEx loop) {
338 Map<Node, InductionVariable> ivs = newIdentityMap();
339
340 Queue<InductionVariable> scanQueue = new LinkedList<>();
341 LoopBeginNode loopBegin = loop.loopBegin();
342 AbstractEndNode forwardEnd = loopBegin.forwardEnd();
343 for (PhiNode phi : loopBegin.phis().filter(ValuePhiNode.class)) {
344 ValueNode backValue = phi.singleBackValue();
345 if (backValue == PhiNode.MULTIPLE_VALUES) {
346 continue;
347 }
348 ValueNode stride = addSub(loop, backValue, phi);
349 if (stride != null) {
350 BasicInductionVariable biv = new BasicInductionVariable(loop, (ValuePhiNode) phi, phi.valueAt(forwardEnd), stride, (BinaryArithmeticNode<?>) backValue);
351 ivs.put(phi, biv);
352 scanQueue.add(biv);
353 }
354 }
355
356 while (!scanQueue.isEmpty()) {
357 InductionVariable baseIv = scanQueue.remove();
358 ValueNode baseIvNode = baseIv.valueNode();
359 for (ValueNode op : baseIvNode.usages().filter(ValueNode.class)) {
360 if (loop.isOutsideLoop(op)) {
361 continue;
362 }
363 if (op.usages().count() == 1 && op.usages().first() == baseIvNode) {
364 /*
365 * This is just the base induction variable increment with no other uses so
377 } else if ((scale = mul(loop, op, baseIvNode)) != null) {
378 iv = new DerivedScaledInductionVariable(loop, baseIv, scale, op);
379 } else {
380 boolean isValidConvert = op instanceof PiNode || op instanceof SignExtendNode;
381 if (!isValidConvert && op instanceof ZeroExtendNode) {
382 IntegerStamp inputStamp = (IntegerStamp) ((ZeroExtendNode) op).getValue().stamp();
383 isValidConvert = inputStamp.isPositive();
384 }
385
386 if (isValidConvert) {
387 iv = new DerivedConvertedInductionVariable(loop, baseIv, op.stamp(), op);
388 }
389 }
390
391 if (iv != null) {
392 ivs.put(op, iv);
393 scanQueue.offer(iv);
394 }
395 }
396 }
397 return Collections.unmodifiableMap(ivs);
398 }
399
400 private static ValueNode addSub(LoopEx loop, ValueNode op, ValueNode base) {
401 if (op.stamp() instanceof IntegerStamp && (op instanceof AddNode || op instanceof SubNode)) {
402 BinaryArithmeticNode<?> aritOp = (BinaryArithmeticNode<?>) op;
403 if (aritOp.getX() == base && loop.isOutsideLoop(aritOp.getY())) {
404 return aritOp.getY();
405 } else if (aritOp.getY() == base && loop.isOutsideLoop(aritOp.getX())) {
406 return aritOp.getX();
407 }
408 }
409 return null;
410 }
411
412 private static ValueNode mul(LoopEx loop, ValueNode op, ValueNode base) {
413 if (op instanceof MulNode) {
414 MulNode mul = (MulNode) op;
415 if (mul.getX() == base && loop.isOutsideLoop(mul.getY())) {
416 return mul.getY();
417 } else if (mul.getY() == base && loop.isOutsideLoop(mul.getX())) {
418 return mul.getX();
419 }
420 }
421 if (op instanceof LeftShiftNode) {
422 LeftShiftNode shift = (LeftShiftNode) op;
423 if (shift.getX() == base && shift.getY().isConstant()) {
424 return ConstantNode.forIntegerStamp(base.stamp(), 1 << shift.getY().asJavaConstant().asInt(), base.graph());
425 }
426 }
427 return null;
428 }
429
430 /**
431 * Deletes any nodes created within the scope of this object that have no usages.
432 */
433 public void deleteUnusedNodes() {
434 if (ivs != null) {
435 for (InductionVariable iv : ivs.values()) {
436 iv.deleteUnusedNodes();
437 }
438 }
439 }
440
441 /**
442 * @return true if all nodes in the loop can be duplicated.
443 */
444 public boolean canDuplicateLoop() {
445 for (Node node : inside().nodes()) {
446 if (node instanceof ControlFlowAnchorNode) {
447 return false;
448 }
449 if (node instanceof FrameState) {
450 FrameState frameState = (FrameState) node;
451 if (frameState.bci == BytecodeFrame.AFTER_EXCEPTION_BCI || frameState.bci == BytecodeFrame.UNWIND_BCI) {
452 return false;
453 }
454 }
455 }
456 return true;
457 }
458 }
|
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.loop;
24
25 import java.util.Collection;
26 import java.util.LinkedList;
27 import java.util.Queue;
28
29 import org.graalvm.compiler.core.common.calc.Condition;
30 import org.graalvm.compiler.core.common.cfg.Loop;
31 import org.graalvm.compiler.core.common.type.IntegerStamp;
32 import org.graalvm.compiler.debug.Debug;
33 import org.graalvm.compiler.debug.GraalError;
34 import org.graalvm.compiler.graph.Node;
35 import org.graalvm.compiler.graph.NodeBitMap;
36 import org.graalvm.compiler.graph.iterators.NodePredicate;
37 import org.graalvm.compiler.loop.InductionVariable.Direction;
38 import org.graalvm.compiler.nodes.AbstractBeginNode;
39 import org.graalvm.compiler.nodes.AbstractEndNode;
40 import org.graalvm.compiler.nodes.ConstantNode;
41 import org.graalvm.compiler.nodes.FixedGuardNode;
42 import org.graalvm.compiler.nodes.FixedNode;
43 import org.graalvm.compiler.nodes.FixedWithNextNode;
44 import org.graalvm.compiler.nodes.FrameState;
45 import org.graalvm.compiler.nodes.FullInfopointNode;
46 import org.graalvm.compiler.nodes.IfNode;
49 import org.graalvm.compiler.nodes.LoopExitNode;
50 import org.graalvm.compiler.nodes.PhiNode;
51 import org.graalvm.compiler.nodes.PiNode;
52 import org.graalvm.compiler.nodes.StructuredGraph;
53 import org.graalvm.compiler.nodes.ValueNode;
54 import org.graalvm.compiler.nodes.ValuePhiNode;
55 import org.graalvm.compiler.nodes.calc.AddNode;
56 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
57 import org.graalvm.compiler.nodes.calc.CompareNode;
58 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
59 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
60 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
61 import org.graalvm.compiler.nodes.calc.LeftShiftNode;
62 import org.graalvm.compiler.nodes.calc.MulNode;
63 import org.graalvm.compiler.nodes.calc.NegateNode;
64 import org.graalvm.compiler.nodes.calc.SignExtendNode;
65 import org.graalvm.compiler.nodes.calc.SubNode;
66 import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
67 import org.graalvm.compiler.nodes.cfg.Block;
68 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
69 import org.graalvm.compiler.nodes.debug.ControlFlowAnchored;
70 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
71 import org.graalvm.compiler.nodes.util.GraphUtil;
72 import org.graalvm.util.Equivalence;
73 import org.graalvm.util.EconomicMap;
74
75 import jdk.vm.ci.code.BytecodeFrame;
76
77 public class LoopEx {
78 private final Loop<Block> loop;
79 private LoopFragmentInside inside;
80 private LoopFragmentWhole whole;
81 private CountedLoopInfo counted;
82 private LoopsData data;
83 private EconomicMap<Node, InductionVariable> ivs;
84
85 LoopEx(Loop<Block> loop, LoopsData data) {
86 this.loop = loop;
87 this.data = data;
88 }
89
90 public Loop<Block> loop() {
91 return loop;
92 }
93
94 public LoopFragmentInside inside() {
95 if (inside == null) {
96 inside = new LoopFragmentInside(this);
97 }
98 return inside;
99 }
100
101 public LoopFragmentWhole whole() {
102 if (whole == null) {
103 whole = new LoopFragmentWhole(this);
160 @Override
161 public String toString() {
162 return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + loop().getDepth() + ") " + loopBegin();
163 }
164
165 private class InvariantPredicate implements NodePredicate {
166
167 @Override
168 public boolean apply(Node n) {
169 return isOutsideLoop(n);
170 }
171 }
172
173 public void reassociateInvariants() {
174 InvariantPredicate invariant = new InvariantPredicate();
175 StructuredGraph graph = loopBegin().graph();
176 for (BinaryArithmeticNode<?> binary : whole().nodes().filter(BinaryArithmeticNode.class)) {
177 if (!binary.isAssociative()) {
178 continue;
179 }
180 ValueNode result = BinaryArithmeticNode.reassociate(binary, invariant, binary.getX(), binary.getY());
181 if (result != binary) {
182 if (Debug.isLogEnabled()) {
183 Debug.log("%s : Reassociated %s into %s", graph.method().format("%H::%n"), binary, result);
184 }
185 if (!result.isAlive()) {
186 assert !result.isDeleted();
187 result = graph.addOrUniqueWithInputs(result);
188 }
189 binary.replaceAtUsages(result);
190 GraphUtil.killWithUnusedFloatingInputs(binary);
191 }
192 }
193 }
194
195 public boolean detectCounted() {
196 LoopBeginNode loopBegin = loopBegin();
197 FixedNode next = loopBegin.next();
198 while (next instanceof FixedGuardNode || next instanceof ValueAnchorNode || next instanceof FullInfopointNode) {
199 next = ((FixedWithNextNode) next).next();
200 }
290 }
291 return false;
292 }
293
294 public LoopsData loopsData() {
295 return data;
296 }
297
298 public void nodesInLoopBranch(NodeBitMap branchNodes, AbstractBeginNode branch) {
299 Collection<AbstractBeginNode> blocks = new LinkedList<>();
300 Collection<LoopExitNode> exits = new LinkedList<>();
301 Queue<Block> work = new LinkedList<>();
302 ControlFlowGraph cfg = loopsData().getCFG();
303 work.add(cfg.blockFor(branch));
304 while (!work.isEmpty()) {
305 Block b = work.remove();
306 if (loop().getExits().contains(b)) {
307 exits.add((LoopExitNode) b.getBeginNode());
308 } else {
309 blocks.add(b.getBeginNode());
310 Block d = b.getDominatedSibling();
311 while (d != null) {
312 if (loop.getBlocks().contains(d)) {
313 work.add(d);
314 }
315 d = d.getDominatedSibling();
316 }
317 }
318 }
319 LoopFragment.computeNodes(branchNodes, branch.graph(), blocks, exits);
320 }
321
322 public EconomicMap<Node, InductionVariable> getInductionVariables() {
323 if (ivs == null) {
324 ivs = findInductionVariables(this);
325 }
326 return ivs;
327 }
328
329 /**
330 * Collect all the basic induction variables for the loop and the find any induction variables
331 * which are derived from the basic ones.
332 *
333 * @param loop
334 * @return a map from node to induction variable
335 */
336 private static EconomicMap<Node, InductionVariable> findInductionVariables(LoopEx loop) {
337 EconomicMap<Node, InductionVariable> ivs = EconomicMap.create(Equivalence.IDENTITY);
338
339 Queue<InductionVariable> scanQueue = new LinkedList<>();
340 LoopBeginNode loopBegin = loop.loopBegin();
341 AbstractEndNode forwardEnd = loopBegin.forwardEnd();
342 for (PhiNode phi : loopBegin.valuePhis()) {
343 ValueNode backValue = phi.singleBackValueOrThis();
344 if (backValue == phi) {
345 continue;
346 }
347 ValueNode stride = addSub(loop, backValue, phi);
348 if (stride != null) {
349 BasicInductionVariable biv = new BasicInductionVariable(loop, (ValuePhiNode) phi, phi.valueAt(forwardEnd), stride, (BinaryArithmeticNode<?>) backValue);
350 ivs.put(phi, biv);
351 scanQueue.add(biv);
352 }
353 }
354
355 while (!scanQueue.isEmpty()) {
356 InductionVariable baseIv = scanQueue.remove();
357 ValueNode baseIvNode = baseIv.valueNode();
358 for (ValueNode op : baseIvNode.usages().filter(ValueNode.class)) {
359 if (loop.isOutsideLoop(op)) {
360 continue;
361 }
362 if (op.usages().count() == 1 && op.usages().first() == baseIvNode) {
363 /*
364 * This is just the base induction variable increment with no other uses so
376 } else if ((scale = mul(loop, op, baseIvNode)) != null) {
377 iv = new DerivedScaledInductionVariable(loop, baseIv, scale, op);
378 } else {
379 boolean isValidConvert = op instanceof PiNode || op instanceof SignExtendNode;
380 if (!isValidConvert && op instanceof ZeroExtendNode) {
381 IntegerStamp inputStamp = (IntegerStamp) ((ZeroExtendNode) op).getValue().stamp();
382 isValidConvert = inputStamp.isPositive();
383 }
384
385 if (isValidConvert) {
386 iv = new DerivedConvertedInductionVariable(loop, baseIv, op.stamp(), op);
387 }
388 }
389
390 if (iv != null) {
391 ivs.put(op, iv);
392 scanQueue.offer(iv);
393 }
394 }
395 }
396 return ivs;
397 }
398
399 private static ValueNode addSub(LoopEx loop, ValueNode op, ValueNode base) {
400 if (op.stamp() instanceof IntegerStamp && (op instanceof AddNode || op instanceof SubNode)) {
401 BinaryArithmeticNode<?> aritOp = (BinaryArithmeticNode<?>) op;
402 if (aritOp.getX() == base && loop.isOutsideLoop(aritOp.getY())) {
403 return aritOp.getY();
404 } else if (aritOp.getY() == base && loop.isOutsideLoop(aritOp.getX())) {
405 return aritOp.getX();
406 }
407 }
408 return null;
409 }
410
411 private static ValueNode mul(LoopEx loop, ValueNode op, ValueNode base) {
412 if (op instanceof MulNode) {
413 MulNode mul = (MulNode) op;
414 if (mul.getX() == base && loop.isOutsideLoop(mul.getY())) {
415 return mul.getY();
416 } else if (mul.getY() == base && loop.isOutsideLoop(mul.getX())) {
417 return mul.getX();
418 }
419 }
420 if (op instanceof LeftShiftNode) {
421 LeftShiftNode shift = (LeftShiftNode) op;
422 if (shift.getX() == base && shift.getY().isConstant()) {
423 return ConstantNode.forIntegerStamp(base.stamp(), 1 << shift.getY().asJavaConstant().asInt(), base.graph());
424 }
425 }
426 return null;
427 }
428
429 /**
430 * Deletes any nodes created within the scope of this object that have no usages.
431 */
432 public void deleteUnusedNodes() {
433 if (ivs != null) {
434 for (InductionVariable iv : ivs.getValues()) {
435 iv.deleteUnusedNodes();
436 }
437 }
438 }
439
440 /**
441 * @return true if all nodes in the loop can be duplicated.
442 */
443 public boolean canDuplicateLoop() {
444 for (Node node : inside().nodes()) {
445 if (node instanceof ControlFlowAnchored) {
446 return false;
447 }
448 if (node instanceof FrameState) {
449 FrameState frameState = (FrameState) node;
450 if (frameState.bci == BytecodeFrame.AFTER_EXCEPTION_BCI || frameState.bci == BytecodeFrame.UNWIND_BCI) {
451 return false;
452 }
453 }
454 }
455 return true;
456 }
457 }
|