1 /*
2 * Copyright (c) 2012, 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.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;
47 import org.graalvm.compiler.nodes.LogicNode;
48 import org.graalvm.compiler.nodes.LoopBeginNode;
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.EconomicMap;
73 import org.graalvm.util.EconomicSet;
74 import org.graalvm.util.Equivalence;
75
76 import jdk.vm.ci.code.BytecodeFrame;
77
78 public class LoopEx {
79 private final Loop<Block> loop;
80 private LoopFragmentInside inside;
81 private LoopFragmentWhole whole;
82 private CountedLoopInfo counted;
83 private LoopsData data;
84 private EconomicMap<Node, InductionVariable> ivs;
85
86 LoopEx(Loop<Block> loop, LoopsData data) {
87 this.loop = loop;
88 this.data = data;
89 }
90
91 public Loop<Block> loop() {
92 return loop;
93 }
94
95 public LoopFragmentInside inside() {
96 if (inside == null) {
97 inside = new LoopFragmentInside(this);
98 }
99 return inside;
100 }
101
102 public LoopFragmentWhole whole() {
103 if (whole == null) {
104 whole = new LoopFragmentWhole(this);
105 }
106 return whole;
107 }
108
109 public void invalidateFragments() {
110 inside = null;
111 whole = null;
112 }
113
114 @SuppressWarnings("unused")
115 public LoopFragmentInsideFrom insideFrom(FixedNode point) {
116 // TODO (gd)
117 return null;
118 }
119
120 @SuppressWarnings("unused")
121 public LoopFragmentInsideBefore insideBefore(FixedNode point) {
122 // TODO (gd)
123 return null;
124 }
125
126 public boolean isOutsideLoop(Node n) {
127 return !whole().contains(n);
128 }
129
130 public LoopBeginNode loopBegin() {
131 return (LoopBeginNode) loop().getHeader().getBeginNode();
132 }
133
134 public FixedNode predecessor() {
135 return (FixedNode) loopBegin().forwardEnd().predecessor();
136 }
137
138 public FixedNode entryPoint() {
139 return loopBegin().forwardEnd();
140 }
141
142 public boolean isCounted() {
143 return counted != null;
144 }
145
146 public CountedLoopInfo counted() {
147 return counted;
148 }
149
150 public LoopEx parent() {
151 if (loop.getParent() == null) {
152 return null;
153 }
154 return data.loop(loop.getParent());
155 }
156
157 public int size() {
158 return whole().nodes().count();
159 }
160
161 @Override
162 public String toString() {
163 return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + loop().getDepth() + ") " + loopBegin();
164 }
165
166 private class InvariantPredicate implements NodePredicate {
167
168 @Override
169 public boolean apply(Node n) {
170 return isOutsideLoop(n);
171 }
172 }
173
174 public void reassociateInvariants() {
175 InvariantPredicate invariant = new InvariantPredicate();
176 StructuredGraph graph = loopBegin().graph();
177 for (BinaryArithmeticNode<?> binary : whole().nodes().filter(BinaryArithmeticNode.class)) {
178 if (!binary.isAssociative()) {
179 continue;
180 }
181 ValueNode result = BinaryArithmeticNode.reassociate(binary, invariant, binary.getX(), binary.getY());
182 if (result != binary) {
183 if (Debug.isLogEnabled()) {
184 Debug.log("%s : Reassociated %s into %s", graph.method().format("%H::%n"), binary, result);
185 }
186 if (!result.isAlive()) {
187 assert !result.isDeleted();
188 result = graph.addOrUniqueWithInputs(result);
189 }
190 binary.replaceAtUsages(result);
191 GraphUtil.killWithUnusedFloatingInputs(binary);
192 }
193 }
194 }
195
196 public boolean detectCounted() {
197 LoopBeginNode loopBegin = loopBegin();
198 FixedNode next = loopBegin.next();
199 while (next instanceof FixedGuardNode || next instanceof ValueAnchorNode || next instanceof FullInfopointNode) {
200 next = ((FixedWithNextNode) next).next();
201 }
202 if (next instanceof IfNode) {
203 IfNode ifNode = (IfNode) next;
204 boolean negated = false;
205 if (!loopBegin.isLoopExit(ifNode.falseSuccessor())) {
206 if (!loopBegin.isLoopExit(ifNode.trueSuccessor())) {
207 return false;
208 }
209 negated = true;
210 }
211 LogicNode ifTest = ifNode.condition();
212 if (!(ifTest instanceof IntegerLessThanNode) && !(ifTest instanceof IntegerEqualsNode)) {
213 if (ifTest instanceof IntegerBelowNode) {
214 Debug.log("Ignored potential Counted loop at %s with |<|", loopBegin);
215 }
216 return false;
217 }
218 CompareNode lessThan = (CompareNode) ifTest;
219 Condition condition = null;
220 InductionVariable iv = null;
221 ValueNode limit = null;
222 if (isOutsideLoop(lessThan.getX())) {
223 iv = getInductionVariables().get(lessThan.getY());
224 if (iv != null) {
225 condition = lessThan.condition().mirror();
226 limit = lessThan.getX();
227 }
228 } else if (isOutsideLoop(lessThan.getY())) {
229 iv = getInductionVariables().get(lessThan.getX());
230 if (iv != null) {
231 condition = lessThan.condition();
232 limit = lessThan.getY();
233 }
234 }
235 if (condition == null) {
236 return false;
237 }
238 if (negated) {
239 condition = condition.negate();
240 }
241 boolean oneOff = false;
242 switch (condition) {
243 case EQ:
244 return false;
245 case NE: {
246 if (!iv.isConstantStride() || Math.abs(iv.constantStride()) != 1) {
247 return false;
248 }
249 IntegerStamp initStamp = (IntegerStamp) iv.initNode().stamp();
250 IntegerStamp limitStamp = (IntegerStamp) limit.stamp();
251 if (iv.direction() == Direction.Up) {
252 if (initStamp.upperBound() > limitStamp.lowerBound()) {
253 return false;
254 }
255 } else if (iv.direction() == Direction.Down) {
256 if (initStamp.lowerBound() < limitStamp.upperBound()) {
257 return false;
258 }
259 } else {
260 return false;
261 }
262 break;
263 }
264 case LE:
265 oneOff = true;
266 if (iv.direction() != Direction.Up) {
267 return false;
268 }
269 break;
270 case LT:
271 if (iv.direction() != Direction.Up) {
272 return false;
273 }
274 break;
275 case GE:
276 oneOff = true;
277 if (iv.direction() != Direction.Down) {
278 return false;
279 }
280 break;
281 case GT:
282 if (iv.direction() != Direction.Down) {
283 return false;
284 }
285 break;
286 default:
287 throw GraalError.shouldNotReachHere();
288 }
289 counted = new CountedLoopInfo(this, iv, limit, oneOff, negated ? ifNode.falseSuccessor() : ifNode.trueSuccessor());
290 return true;
291 }
292 return false;
293 }
294
295 public LoopsData loopsData() {
296 return data;
297 }
298
299 public void nodesInLoopBranch(NodeBitMap branchNodes, AbstractBeginNode branch) {
300 EconomicSet<AbstractBeginNode> blocks = EconomicSet.create();
301 Collection<LoopExitNode> exits = new LinkedList<>();
302 Queue<Block> work = new LinkedList<>();
303 ControlFlowGraph cfg = loopsData().getCFG();
304 work.add(cfg.blockFor(branch));
305 while (!work.isEmpty()) {
306 Block b = work.remove();
307 if (loop().getExits().contains(b)) {
308 assert !exits.contains(b.getBeginNode());
309 exits.add((LoopExitNode) b.getBeginNode());
310 } else if (blocks.add(b.getBeginNode())) {
311 Block d = b.getDominatedSibling();
312 while (d != null) {
313 if (loop.getBlocks().contains(d)) {
314 work.add(d);
315 }
316 d = d.getDominatedSibling();
317 }
318 }
319 }
320 LoopFragment.computeNodes(branchNodes, branch.graph(), blocks, exits);
321 }
322
323 public EconomicMap<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 EconomicMap<Node, InductionVariable> findInductionVariables(LoopEx loop) {
338 EconomicMap<Node, InductionVariable> ivs = EconomicMap.create(Equivalence.IDENTITY);
339
340 Queue<InductionVariable> scanQueue = new LinkedList<>();
341 LoopBeginNode loopBegin = loop.loopBegin();
342 AbstractEndNode forwardEnd = loopBegin.forwardEnd();
343 for (PhiNode phi : loopBegin.valuePhis()) {
344 ValueNode backValue = phi.singleBackValueOrThis();
345 if (backValue == phi) {
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
366 * don't bother reporting it.
367 */
368 continue;
369 }
370 InductionVariable iv = null;
371 ValueNode offset = addSub(loop, op, baseIvNode);
372 ValueNode scale;
373 if (offset != null) {
374 iv = new DerivedOffsetInductionVariable(loop, baseIv, offset, (BinaryArithmeticNode<?>) op);
375 } else if (op instanceof NegateNode) {
376 iv = new DerivedScaledInductionVariable(loop, baseIv, (NegateNode) op);
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 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.getValues()) {
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 ControlFlowAnchored) {
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 }