39 import org.graalvm.compiler.nodes.AbstractBeginNode;
40 import org.graalvm.compiler.nodes.AbstractMergeNode;
41 import org.graalvm.compiler.nodes.EndNode;
42 import org.graalvm.compiler.nodes.FixedNode;
43 import org.graalvm.compiler.nodes.FrameState;
44 import org.graalvm.compiler.nodes.GuardNode;
45 import org.graalvm.compiler.nodes.GuardPhiNode;
46 import org.graalvm.compiler.nodes.GuardProxyNode;
47 import org.graalvm.compiler.nodes.Invoke;
48 import org.graalvm.compiler.nodes.LoopExitNode;
49 import org.graalvm.compiler.nodes.MergeNode;
50 import org.graalvm.compiler.nodes.NodeView;
51 import org.graalvm.compiler.nodes.PhiNode;
52 import org.graalvm.compiler.nodes.ProxyNode;
53 import org.graalvm.compiler.nodes.StructuredGraph;
54 import org.graalvm.compiler.nodes.ValueNode;
55 import org.graalvm.compiler.nodes.ValuePhiNode;
56 import org.graalvm.compiler.nodes.ValueProxyNode;
57 import org.graalvm.compiler.nodes.VirtualState;
58 import org.graalvm.compiler.nodes.cfg.Block;
59 import org.graalvm.compiler.nodes.java.MonitorEnterNode;
60 import org.graalvm.compiler.nodes.spi.NodeWithState;
61 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
62 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
63
64 import jdk.vm.ci.meta.TriState;
65
66 public abstract class LoopFragment {
67
68 private final LoopEx loop;
69 private final LoopFragment original;
70 protected NodeBitMap nodes;
71 protected boolean nodesReady;
72 private EconomicMap<Node, Node> duplicationMap;
73
74 public LoopFragment(LoopEx loop) {
75 this(loop, null);
76 this.nodesReady = true;
77 }
78
127 public LoopFragment original() {
128 return original;
129 }
130
131 public abstract NodeBitMap nodes();
132
133 public StructuredGraph graph() {
134 LoopEx l;
135 if (isDuplicate()) {
136 l = original().loop();
137 } else {
138 l = loop();
139 }
140 return l.loopBegin().graph();
141 }
142
143 protected abstract DuplicationReplacement getDuplicationReplacement();
144
145 protected abstract void beforeDuplication();
146
147 protected abstract void finishDuplication();
148
149 protected void patchNodes(final DuplicationReplacement dataFix) {
150 if (isDuplicate() && !nodesReady) {
151 assert !original.isDuplicate();
152 final DuplicationReplacement cfgFix = original().getDuplicationReplacement();
153 DuplicationReplacement dr;
154 if (cfgFix == null && dataFix != null) {
155 dr = dataFix;
156 } else if (cfgFix != null && dataFix == null) {
157 dr = cfgFix;
158 } else if (cfgFix != null && dataFix != null) {
159 dr = new DuplicationReplacement() {
160
161 @Override
162 public Node replacement(Node o) {
163 Node r1 = dataFix.replacement(o);
164 if (r1 != o) {
165 assert cfgFix.replacement(o) == o;
166 return r1;
167 }
371 @Override
372 public void remove() {
373 throw new UnsupportedOperationException();
374 }
375
376 @Override
377 public AbstractBeginNode next() {
378 return it.next().getBeginNode();
379 }
380
381 @Override
382 public boolean hasNext() {
383 return it.hasNext();
384 }
385 };
386 }
387
388 };
389 }
390
391 public static NodeIterable<AbstractBeginNode> toHirExits(final Iterable<Block> blocks) {
392 return new NodeIterable<AbstractBeginNode>() {
393
394 @Override
395 public Iterator<AbstractBeginNode> iterator() {
396 final Iterator<Block> it = blocks.iterator();
397 return new Iterator<AbstractBeginNode>() {
398
399 @Override
400 public void remove() {
401 throw new UnsupportedOperationException();
402 }
403
404 /**
405 * Return the true LoopExitNode for this loop or the BeginNode for the block.
406 */
407 @Override
408 public AbstractBeginNode next() {
409 Block next = it.next();
410 LoopExitNode exit = next.getLoopExit();
411 if (exit != null) {
412 return exit;
413 }
414 return next.getBeginNode();
415 }
416
417 @Override
418 public boolean hasNext() {
419 return it.hasNext();
420 }
421 };
422 }
423
424 };
425 }
426
427 /**
428 * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with
429 * the original fragment's exits.
430 */
431 protected void mergeEarlyExits() {
432 assert isDuplicate();
433 StructuredGraph graph = graph();
434 for (AbstractBeginNode earlyExit : LoopFragment.toHirBlocks(original().loop().loop().getExits())) {
435 LoopExitNode loopEarlyExit = (LoopExitNode) earlyExit;
436 FixedNode next = loopEarlyExit.next();
437 if (loopEarlyExit.isDeleted() || !this.original().contains(loopEarlyExit)) {
438 continue;
439 }
440 AbstractBeginNode newEarlyExit = getDuplicatedNode(loopEarlyExit);
441 if (newEarlyExit == null) {
442 continue;
443 }
444 MergeNode merge = graph.add(new MergeNode());
445 EndNode originalEnd = graph.add(new EndNode());
446 EndNode newEnd = graph.add(new EndNode());
447 merge.addForwardEnd(originalEnd);
448 merge.addForwardEnd(newEnd);
449 loopEarlyExit.setNext(originalEnd);
450 newEarlyExit.setNext(newEnd);
451 merge.setNext(next);
452
453 FrameState exitState = loopEarlyExit.stateAfter();
454 if (exitState != null) {
455 FrameState originalExitState = exitState;
456 exitState = exitState.duplicateWithVirtualState();
457 loopEarlyExit.setStateAfter(exitState);
458 merge.setStateAfter(originalExitState);
459 /*
460 * Using the old exit's state as the merge's state is necessary because some of the
461 * VirtualState nodes contained in the old exit's state may be shared by other
462 * dominated VirtualStates. Those dominated virtual states need to see the
463 * proxy->phi update that are applied below.
464 *
465 * We now update the original fragment's nodes accordingly:
466 */
467 originalExitState.applyToVirtual(node -> original.nodes.clearAndGrow(node));
468 exitState.applyToVirtual(node -> original.nodes.markAndGrow(node));
469 }
470 FrameState finalExitState = exitState;
471
472 for (Node anchored : loopEarlyExit.anchored().snapshot()) {
473 anchored.replaceFirstInput(loopEarlyExit, merge);
474 }
475
476 boolean newEarlyExitIsLoopExit = newEarlyExit instanceof LoopExitNode;
477 for (ProxyNode vpn : loopEarlyExit.proxies().snapshot()) {
478 if (vpn.hasNoUsages()) {
479 continue;
480 }
481 if (vpn.value() == null) {
482 assert vpn instanceof GuardProxyNode;
483 vpn.replaceAtUsages(null);
484 continue;
485 }
486 final ValueNode replaceWith;
487 ValueNode newVpn = prim(newEarlyExitIsLoopExit ? vpn : vpn.value());
488 if (newVpn != null) {
489 PhiNode phi;
490 if (vpn instanceof ValueProxyNode) {
491 phi = graph.addWithoutUnique(new ValuePhiNode(vpn.stamp(NodeView.DEFAULT), merge));
492 } else if (vpn instanceof GuardProxyNode) {
493 phi = graph.addWithoutUnique(new GuardPhiNode(merge));
494 } else {
495 throw GraalError.shouldNotReachHere();
496 }
497 phi.addInput(vpn);
498 phi.addInput(newVpn);
499 replaceWith = phi;
500 } else {
501 replaceWith = vpn.value();
502 }
503 vpn.replaceAtMatchingUsages(replaceWith, usage -> {
504 if (merge.isPhiAtMerge(usage)) {
505 return false;
506 }
507 if (usage instanceof VirtualState) {
508 VirtualState stateUsage = (VirtualState) usage;
509 if (finalExitState != null && finalExitState.isPartOfThisState(stateUsage)) {
510 return false;
511 }
512 }
513 return true;
514 });
515 }
516 }
517 }
518 }
|
39 import org.graalvm.compiler.nodes.AbstractBeginNode;
40 import org.graalvm.compiler.nodes.AbstractMergeNode;
41 import org.graalvm.compiler.nodes.EndNode;
42 import org.graalvm.compiler.nodes.FixedNode;
43 import org.graalvm.compiler.nodes.FrameState;
44 import org.graalvm.compiler.nodes.GuardNode;
45 import org.graalvm.compiler.nodes.GuardPhiNode;
46 import org.graalvm.compiler.nodes.GuardProxyNode;
47 import org.graalvm.compiler.nodes.Invoke;
48 import org.graalvm.compiler.nodes.LoopExitNode;
49 import org.graalvm.compiler.nodes.MergeNode;
50 import org.graalvm.compiler.nodes.NodeView;
51 import org.graalvm.compiler.nodes.PhiNode;
52 import org.graalvm.compiler.nodes.ProxyNode;
53 import org.graalvm.compiler.nodes.StructuredGraph;
54 import org.graalvm.compiler.nodes.ValueNode;
55 import org.graalvm.compiler.nodes.ValuePhiNode;
56 import org.graalvm.compiler.nodes.ValueProxyNode;
57 import org.graalvm.compiler.nodes.VirtualState;
58 import org.graalvm.compiler.nodes.cfg.Block;
59 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
60 import org.graalvm.compiler.nodes.java.MonitorEnterNode;
61 import org.graalvm.compiler.nodes.spi.NodeWithState;
62 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
63 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
64
65 import jdk.vm.ci.meta.TriState;
66
67 public abstract class LoopFragment {
68
69 private final LoopEx loop;
70 private final LoopFragment original;
71 protected NodeBitMap nodes;
72 protected boolean nodesReady;
73 private EconomicMap<Node, Node> duplicationMap;
74
75 public LoopFragment(LoopEx loop) {
76 this(loop, null);
77 this.nodesReady = true;
78 }
79
128 public LoopFragment original() {
129 return original;
130 }
131
132 public abstract NodeBitMap nodes();
133
134 public StructuredGraph graph() {
135 LoopEx l;
136 if (isDuplicate()) {
137 l = original().loop();
138 } else {
139 l = loop();
140 }
141 return l.loopBegin().graph();
142 }
143
144 protected abstract DuplicationReplacement getDuplicationReplacement();
145
146 protected abstract void beforeDuplication();
147
148 protected void finishDuplication() {
149 LoopEx originalLoopEx = original().loop();
150 ControlFlowGraph cfg = originalLoopEx.loopsData().getCFG();
151 for (LoopExitNode exit : originalLoopEx.loopBegin().loopExits().snapshot()) {
152 if (!originalLoopEx.loop().isLoopExit(cfg.blockFor(exit))) {
153 // this LoopExitNode is too low, we need to remove it otherwise it will be below
154 // merged exits
155 exit.removeExit();
156 }
157 }
158
159 }
160
161 protected void patchNodes(final DuplicationReplacement dataFix) {
162 if (isDuplicate() && !nodesReady) {
163 assert !original.isDuplicate();
164 final DuplicationReplacement cfgFix = original().getDuplicationReplacement();
165 DuplicationReplacement dr;
166 if (cfgFix == null && dataFix != null) {
167 dr = dataFix;
168 } else if (cfgFix != null && dataFix == null) {
169 dr = cfgFix;
170 } else if (cfgFix != null && dataFix != null) {
171 dr = new DuplicationReplacement() {
172
173 @Override
174 public Node replacement(Node o) {
175 Node r1 = dataFix.replacement(o);
176 if (r1 != o) {
177 assert cfgFix.replacement(o) == o;
178 return r1;
179 }
383 @Override
384 public void remove() {
385 throw new UnsupportedOperationException();
386 }
387
388 @Override
389 public AbstractBeginNode next() {
390 return it.next().getBeginNode();
391 }
392
393 @Override
394 public boolean hasNext() {
395 return it.hasNext();
396 }
397 };
398 }
399
400 };
401 }
402
403 /**
404 * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with
405 * the original fragment's exits.
406 */
407 protected void mergeEarlyExits() {
408 assert isDuplicate();
409 StructuredGraph graph = graph();
410 for (AbstractBeginNode earlyExit : LoopFragment.toHirBlocks(original().loop().loop().getLoopExits())) {
411 FixedNode next = earlyExit.next();
412 if (earlyExit.isDeleted() || !this.original().contains(earlyExit)) {
413 continue;
414 }
415 AbstractBeginNode newEarlyExit = getDuplicatedNode(earlyExit);
416 if (newEarlyExit == null) {
417 continue;
418 }
419 MergeNode merge = graph.add(new MergeNode());
420 EndNode originalEnd = graph.add(new EndNode());
421 EndNode newEnd = graph.add(new EndNode());
422 merge.addForwardEnd(originalEnd);
423 merge.addForwardEnd(newEnd);
424 earlyExit.setNext(originalEnd);
425 newEarlyExit.setNext(newEnd);
426 merge.setNext(next);
427
428 FrameState exitState = null;
429 if (earlyExit instanceof LoopExitNode) {
430 LoopExitNode earlyLoopExit = (LoopExitNode) earlyExit;
431 exitState = earlyLoopExit.stateAfter();
432 if (exitState != null) {
433 FrameState originalExitState = exitState;
434 exitState = exitState.duplicateWithVirtualState();
435 earlyLoopExit.setStateAfter(exitState);
436 merge.setStateAfter(originalExitState);
437 /*
438 * Using the old exit's state as the merge's state is necessary because some of
439 * the VirtualState nodes contained in the old exit's state may be shared by
440 * other dominated VirtualStates. Those dominated virtual states need to see the
441 * proxy->phi update that are applied below.
442 *
443 * We now update the original fragment's nodes accordingly:
444 */
445 originalExitState.applyToVirtual(node -> original.nodes.clearAndGrow(node));
446 exitState.applyToVirtual(node -> original.nodes.markAndGrow(node));
447 }
448 }
449
450 for (Node anchored : earlyExit.anchored().snapshot()) {
451 anchored.replaceFirstInput(earlyExit, merge);
452 }
453
454 if (earlyExit instanceof LoopExitNode) {
455 LoopExitNode earlyLoopExit = (LoopExitNode) earlyExit;
456 FrameState finalExitState = exitState;
457 boolean newEarlyExitIsLoopExit = newEarlyExit instanceof LoopExitNode;
458 for (ProxyNode vpn : earlyLoopExit.proxies().snapshot()) {
459 if (vpn.hasNoUsages()) {
460 continue;
461 }
462 if (vpn.value() == null) {
463 assert vpn instanceof GuardProxyNode;
464 vpn.replaceAtUsages(null);
465 continue;
466 }
467 final ValueNode replaceWith;
468 ValueNode newVpn = prim(newEarlyExitIsLoopExit ? vpn : vpn.value());
469 if (newVpn != null) {
470 PhiNode phi;
471 if (vpn instanceof ValueProxyNode) {
472 phi = graph.addWithoutUnique(new ValuePhiNode(vpn.stamp(NodeView.DEFAULT), merge));
473 } else if (vpn instanceof GuardProxyNode) {
474 phi = graph.addWithoutUnique(new GuardPhiNode(merge));
475 } else {
476 throw GraalError.shouldNotReachHere();
477 }
478 phi.addInput(vpn);
479 phi.addInput(newVpn);
480 replaceWith = phi;
481 } else {
482 replaceWith = vpn.value();
483 }
484 vpn.replaceAtMatchingUsages(replaceWith, usage -> {
485 if (merge.isPhiAtMerge(usage)) {
486 return false;
487 }
488 if (usage instanceof VirtualState) {
489 VirtualState stateUsage = (VirtualState) usage;
490 if (finalExitState != null && finalExitState.isPartOfThisState(stateUsage)) {
491 return false;
492 }
493 }
494 return true;
495 });
496 }
497 }
498 }
499 }
500 }
|