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 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;
51 import org.graalvm.compiler.nodes.LogicNode;
52 import org.graalvm.compiler.nodes.LoopBeginNode;
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);
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 return counted != null;
146 }
147
148 public CountedLoopInfo counted() {
149 return counted;
150 }
151
152 public LoopEx parent() {
153 if (loop.getParent() == null) {
154 return null;
155 }
156 return data.loop(loop.getParent());
157 }
158
159 public int size() {
160 return whole().nodes().count();
161 }
162
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 }
204 if (next instanceof IfNode) {
205 IfNode ifNode = (IfNode) next;
206 boolean negated = false;
207 if (!loopBegin.isLoopExit(ifNode.falseSuccessor())) {
208 if (!loopBegin.isLoopExit(ifNode.trueSuccessor())) {
209 return false;
210 }
211 negated = true;
212 }
213 LogicNode ifTest = ifNode.condition();
214 if (!(ifTest instanceof IntegerLessThanNode) && !(ifTest instanceof IntegerEqualsNode)) {
215 if (ifTest instanceof IntegerBelowNode) {
216 Debug.log("Ignored potential Counted loop at %s with |<|", loopBegin);
217 }
218 return false;
219 }
220 CompareNode lessThan = (CompareNode) ifTest;
221 Condition condition = null;
222 InductionVariable iv = null;
223 ValueNode limit = null;
224 if (isOutsideLoop(lessThan.getX())) {
225 iv = getInductionVariables().get(lessThan.getY());
226 if (iv != null) {
227 condition = lessThan.condition().mirror();
228 limit = lessThan.getX();
229 }
230 } else if (isOutsideLoop(lessThan.getY())) {
231 iv = getInductionVariables().get(lessThan.getX());
232 if (iv != null) {
233 condition = lessThan.condition();
234 limit = lessThan.getY();
235 }
236 }
237 if (condition == null) {
238 return false;
239 }
240 if (negated) {
241 condition = condition.negate();
242 }
243 boolean oneOff = false;
244 switch (condition) {
245 case EQ:
246 return false;
247 case NE: {
248 if (!iv.isConstantStride() || Math.abs(iv.constantStride()) != 1) {
249 return false;
250 }
251 IntegerStamp initStamp = (IntegerStamp) iv.initNode().stamp();
252 IntegerStamp limitStamp = (IntegerStamp) limit.stamp();
253 if (iv.direction() == Direction.Up) {
254 if (initStamp.upperBound() > limitStamp.lowerBound()) {
255 return false;
256 }
257 } else if (iv.direction() == Direction.Down) {
258 if (initStamp.lowerBound() < limitStamp.upperBound()) {
259 return false;
260 }
261 } else {
262 return false;
263 }
264 break;
265 }
266 case LE:
267 oneOff = true;
268 if (iv.direction() != Direction.Up) {
269 return false;
270 }
271 break;
272 case LT:
273 if (iv.direction() != Direction.Up) {
274 return false;
275 }
276 break;
277 case GE:
278 oneOff = true;
279 if (iv.direction() != Direction.Down) {
280 return false;
281 }
282 break;
283 case GT:
284 if (iv.direction() != Direction.Down) {
285 return false;
286 }
287 break;
288 default:
289 throw GraalError.shouldNotReachHere();
290 }
291 counted = new CountedLoopInfo(this, iv, limit, oneOff, negated ? ifNode.falseSuccessor() : ifNode.trueSuccessor());
292 return true;
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
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 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 }