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.LinkedList;
26 import java.util.List;
27 import java.util.Map;
28
29 import org.graalvm.compiler.core.common.CollectionsFactory;
30 import org.graalvm.compiler.debug.GraalError;
31 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
32 import org.graalvm.compiler.graph.Node;
33 import org.graalvm.compiler.graph.NodeBitMap;
34 import org.graalvm.compiler.graph.iterators.NodeIterable;
35 import org.graalvm.compiler.nodes.AbstractBeginNode;
36 import org.graalvm.compiler.nodes.AbstractEndNode;
37 import org.graalvm.compiler.nodes.AbstractMergeNode;
38 import org.graalvm.compiler.nodes.BeginNode;
39 import org.graalvm.compiler.nodes.EndNode;
40 import org.graalvm.compiler.nodes.FrameState;
41 import org.graalvm.compiler.nodes.GuardPhiNode;
42 import org.graalvm.compiler.nodes.LoopBeginNode;
43 import org.graalvm.compiler.nodes.LoopEndNode;
44 import org.graalvm.compiler.nodes.LoopExitNode;
45 import org.graalvm.compiler.nodes.MergeNode;
46 import org.graalvm.compiler.nodes.PhiNode;
47 import org.graalvm.compiler.nodes.ProxyNode;
48 import org.graalvm.compiler.nodes.StateSplit;
49 import org.graalvm.compiler.nodes.StructuredGraph;
50 import org.graalvm.compiler.nodes.ValueNode;
51 import org.graalvm.compiler.nodes.ValuePhiNode;
52 import org.graalvm.compiler.nodes.VirtualState.NodeClosure;
53 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
54 import org.graalvm.compiler.nodes.util.GraphUtil;
55
56 public class LoopFragmentInside extends LoopFragment {
57
58 /**
59 * mergedInitializers. When an inside fragment's (loop)ends are merged to create a unique exit
60 * point, some phis must be created : they phis together all the back-values of the loop-phis
61 * These can then be used to update the loop-phis' forward edge value ('initializer') in the
62 * peeling case. In the unrolling case they will be used as the value that replace the loop-phis
63 * of the duplicated inside fragment
64 */
65 private Map<ValuePhiNode, ValueNode> mergedInitializers;
66 private final DuplicationReplacement dataFixBefore = new DuplicationReplacement() {
67
68 @Override
69 public Node replacement(Node oriInput) {
70 if (!(oriInput instanceof ValueNode)) {
71 return oriInput;
72 }
73 return prim((ValueNode) oriInput);
74 }
75 };
76
77 public LoopFragmentInside(LoopEx loop) {
78 super(loop);
79 }
80
81 public LoopFragmentInside(LoopFragmentInside original) {
82 super(null, original);
83 }
84
85 @Override
147 FrameState loopState = stateSplit.stateAfter();
148 if (loopState != null) {
149 loopState.applyToVirtual(v -> {
150 if (v.usages().filter(n -> nodes.isMarked(n) && n != stateSplit).isEmpty()) {
151 nodes.clear(v);
152 }
153 });
154 }
155 }
156
157 public NodeIterable<LoopExitNode> exits() {
158 return loop().loopBegin().loopExits();
159 }
160
161 @Override
162 protected DuplicationReplacement getDuplicationReplacement() {
163 final LoopBeginNode loopBegin = loop().loopBegin();
164 final StructuredGraph graph = graph();
165 return new DuplicationReplacement() {
166
167 private Map<Node, Node> seenNode = Node.newMap();
168
169 @Override
170 public Node replacement(Node original) {
171 if (original == loopBegin) {
172 Node value = seenNode.get(original);
173 if (value != null) {
174 return value;
175 }
176 AbstractBeginNode newValue = graph.add(new BeginNode());
177 seenNode.put(original, newValue);
178 return newValue;
179 }
180 if (original instanceof LoopExitNode && ((LoopExitNode) original).loopBegin() == loopBegin) {
181 Node value = seenNode.get(original);
182 if (value != null) {
183 return value;
184 }
185 AbstractBeginNode newValue = graph.add(new BeginNode());
186 seenNode.put(original, newValue);
187 return newValue;
324 assert isDuplicate();
325 LoopBeginNode loopBegin = original().loop().loopBegin();
326 if (loopBegin.isPhiAtMerge(b)) {
327 PhiNode phi = (PhiNode) b;
328 return phi.valueAt(loopBegin.forwardEnd());
329 } else if (nodesReady) {
330 ValueNode v = getDuplicatedNode(b);
331 if (v == null) {
332 return b;
333 }
334 return v;
335 } else {
336 return b;
337 }
338 }
339
340 private AbstractBeginNode mergeEnds() {
341 assert isDuplicate();
342 List<EndNode> endsToMerge = new LinkedList<>();
343 // map peel exits to the corresponding loop exits
344 Map<AbstractEndNode, LoopEndNode> reverseEnds = CollectionsFactory.newMap();
345 LoopBeginNode loopBegin = original().loop().loopBegin();
346 for (LoopEndNode le : loopBegin.loopEnds()) {
347 AbstractEndNode duplicate = getDuplicatedNode(le);
348 if (duplicate != null) {
349 endsToMerge.add((EndNode) duplicate);
350 reverseEnds.put(duplicate, le);
351 }
352 }
353 mergedInitializers = Node.newIdentityMap();
354 AbstractBeginNode newExit;
355 StructuredGraph graph = graph();
356 if (endsToMerge.size() == 1) {
357 AbstractEndNode end = endsToMerge.get(0);
358 assert end.hasNoUsages();
359 newExit = graph.add(new BeginNode());
360 end.replaceAtPredecessor(newExit);
361 end.safeDelete();
362 } else {
363 assert endsToMerge.size() > 1;
364 AbstractMergeNode newExitMerge = graph.add(new MergeNode());
365 newExit = newExitMerge;
366 FrameState state = loopBegin.stateAfter();
367 FrameState duplicateState = null;
368 if (state != null) {
369 duplicateState = state.duplicateWithVirtualState();
370 newExitMerge.setStateAfter(duplicateState);
371 }
372 for (EndNode end : endsToMerge) {
373 newExitMerge.addForwardEnd(end);
380 final PhiNode firstPhi = patchPhi(graph, phi, newExitMerge);
381 for (AbstractEndNode end : newExitMerge.forwardEnds()) {
382 LoopEndNode loopEnd = reverseEnds.get(end);
383 ValueNode prim = prim(phi.valueAt(loopEnd));
384 assert prim != null;
385 firstPhi.addInput(prim);
386 }
387 ValueNode initializer = firstPhi;
388 if (duplicateState != null) {
389 // fix the merge's state after
390 duplicateState.applyToNonVirtual(new NodeClosure<ValueNode>() {
391
392 @Override
393 public void apply(Node from, ValueNode node) {
394 if (node == phi) {
395 from.replaceFirstInput(phi, firstPhi);
396 }
397 }
398 });
399 }
400 mergedInitializers.put((ValuePhiNode) phi, initializer);
401 }
402 }
403 return newExit;
404 }
405 }
|
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.LinkedList;
26 import java.util.List;
27
28 import org.graalvm.compiler.debug.GraalError;
29 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
30 import org.graalvm.compiler.graph.Node;
31 import org.graalvm.compiler.graph.NodeBitMap;
32 import org.graalvm.compiler.graph.iterators.NodeIterable;
33 import org.graalvm.compiler.nodes.AbstractBeginNode;
34 import org.graalvm.compiler.nodes.AbstractEndNode;
35 import org.graalvm.compiler.nodes.AbstractMergeNode;
36 import org.graalvm.compiler.nodes.BeginNode;
37 import org.graalvm.compiler.nodes.EndNode;
38 import org.graalvm.compiler.nodes.FrameState;
39 import org.graalvm.compiler.nodes.GuardPhiNode;
40 import org.graalvm.compiler.nodes.LoopBeginNode;
41 import org.graalvm.compiler.nodes.LoopEndNode;
42 import org.graalvm.compiler.nodes.LoopExitNode;
43 import org.graalvm.compiler.nodes.MergeNode;
44 import org.graalvm.compiler.nodes.PhiNode;
45 import org.graalvm.compiler.nodes.ProxyNode;
46 import org.graalvm.compiler.nodes.StateSplit;
47 import org.graalvm.compiler.nodes.StructuredGraph;
48 import org.graalvm.compiler.nodes.ValueNode;
49 import org.graalvm.compiler.nodes.ValuePhiNode;
50 import org.graalvm.compiler.nodes.VirtualState.NodeClosure;
51 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
52 import org.graalvm.compiler.nodes.util.GraphUtil;
53 import org.graalvm.util.Equivalence;
54 import org.graalvm.util.EconomicMap;
55
56 public class LoopFragmentInside extends LoopFragment {
57
58 /**
59 * mergedInitializers. When an inside fragment's (loop)ends are merged to create a unique exit
60 * point, some phis must be created : they phis together all the back-values of the loop-phis
61 * These can then be used to update the loop-phis' forward edge value ('initializer') in the
62 * peeling case. In the unrolling case they will be used as the value that replace the loop-phis
63 * of the duplicated inside fragment
64 */
65 private EconomicMap<PhiNode, ValueNode> mergedInitializers;
66 private final DuplicationReplacement dataFixBefore = new DuplicationReplacement() {
67
68 @Override
69 public Node replacement(Node oriInput) {
70 if (!(oriInput instanceof ValueNode)) {
71 return oriInput;
72 }
73 return prim((ValueNode) oriInput);
74 }
75 };
76
77 public LoopFragmentInside(LoopEx loop) {
78 super(loop);
79 }
80
81 public LoopFragmentInside(LoopFragmentInside original) {
82 super(null, original);
83 }
84
85 @Override
147 FrameState loopState = stateSplit.stateAfter();
148 if (loopState != null) {
149 loopState.applyToVirtual(v -> {
150 if (v.usages().filter(n -> nodes.isMarked(n) && n != stateSplit).isEmpty()) {
151 nodes.clear(v);
152 }
153 });
154 }
155 }
156
157 public NodeIterable<LoopExitNode> exits() {
158 return loop().loopBegin().loopExits();
159 }
160
161 @Override
162 protected DuplicationReplacement getDuplicationReplacement() {
163 final LoopBeginNode loopBegin = loop().loopBegin();
164 final StructuredGraph graph = graph();
165 return new DuplicationReplacement() {
166
167 private EconomicMap<Node, Node> seenNode = EconomicMap.create(Equivalence.IDENTITY);
168
169 @Override
170 public Node replacement(Node original) {
171 if (original == loopBegin) {
172 Node value = seenNode.get(original);
173 if (value != null) {
174 return value;
175 }
176 AbstractBeginNode newValue = graph.add(new BeginNode());
177 seenNode.put(original, newValue);
178 return newValue;
179 }
180 if (original instanceof LoopExitNode && ((LoopExitNode) original).loopBegin() == loopBegin) {
181 Node value = seenNode.get(original);
182 if (value != null) {
183 return value;
184 }
185 AbstractBeginNode newValue = graph.add(new BeginNode());
186 seenNode.put(original, newValue);
187 return newValue;
324 assert isDuplicate();
325 LoopBeginNode loopBegin = original().loop().loopBegin();
326 if (loopBegin.isPhiAtMerge(b)) {
327 PhiNode phi = (PhiNode) b;
328 return phi.valueAt(loopBegin.forwardEnd());
329 } else if (nodesReady) {
330 ValueNode v = getDuplicatedNode(b);
331 if (v == null) {
332 return b;
333 }
334 return v;
335 } else {
336 return b;
337 }
338 }
339
340 private AbstractBeginNode mergeEnds() {
341 assert isDuplicate();
342 List<EndNode> endsToMerge = new LinkedList<>();
343 // map peel exits to the corresponding loop exits
344 EconomicMap<AbstractEndNode, LoopEndNode> reverseEnds = EconomicMap.create(Equivalence.IDENTITY);
345 LoopBeginNode loopBegin = original().loop().loopBegin();
346 for (LoopEndNode le : loopBegin.loopEnds()) {
347 AbstractEndNode duplicate = getDuplicatedNode(le);
348 if (duplicate != null) {
349 endsToMerge.add((EndNode) duplicate);
350 reverseEnds.put(duplicate, le);
351 }
352 }
353 mergedInitializers = EconomicMap.create(Equivalence.IDENTITY);
354 AbstractBeginNode newExit;
355 StructuredGraph graph = graph();
356 if (endsToMerge.size() == 1) {
357 AbstractEndNode end = endsToMerge.get(0);
358 assert end.hasNoUsages();
359 newExit = graph.add(new BeginNode());
360 end.replaceAtPredecessor(newExit);
361 end.safeDelete();
362 } else {
363 assert endsToMerge.size() > 1;
364 AbstractMergeNode newExitMerge = graph.add(new MergeNode());
365 newExit = newExitMerge;
366 FrameState state = loopBegin.stateAfter();
367 FrameState duplicateState = null;
368 if (state != null) {
369 duplicateState = state.duplicateWithVirtualState();
370 newExitMerge.setStateAfter(duplicateState);
371 }
372 for (EndNode end : endsToMerge) {
373 newExitMerge.addForwardEnd(end);
380 final PhiNode firstPhi = patchPhi(graph, phi, newExitMerge);
381 for (AbstractEndNode end : newExitMerge.forwardEnds()) {
382 LoopEndNode loopEnd = reverseEnds.get(end);
383 ValueNode prim = prim(phi.valueAt(loopEnd));
384 assert prim != null;
385 firstPhi.addInput(prim);
386 }
387 ValueNode initializer = firstPhi;
388 if (duplicateState != null) {
389 // fix the merge's state after
390 duplicateState.applyToNonVirtual(new NodeClosure<ValueNode>() {
391
392 @Override
393 public void apply(Node from, ValueNode node) {
394 if (node == phi) {
395 from.replaceFirstInput(phi, firstPhi);
396 }
397 }
398 });
399 }
400 mergedInitializers.put(phi, initializer);
401 }
402 }
403 return newExit;
404 }
405 }
|