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
24
25 package org.graalvm.compiler.loop;
26
27 import java.util.ArrayList;
28 import java.util.LinkedList;
29 import java.util.List;
30
31 import jdk.internal.vm.compiler.collections.EconomicMap;
32 import jdk.internal.vm.compiler.collections.Equivalence;
33 import org.graalvm.compiler.debug.DebugCloseable;
34 import org.graalvm.compiler.debug.DebugContext;
35 import org.graalvm.compiler.debug.GraalError;
36 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
37 import org.graalvm.compiler.graph.Node;
38 import org.graalvm.compiler.graph.NodeBitMap;
39 import org.graalvm.compiler.graph.iterators.NodeIterable;
40 import org.graalvm.compiler.nodes.AbstractBeginNode;
41 import org.graalvm.compiler.nodes.AbstractEndNode;
42 import org.graalvm.compiler.nodes.AbstractMergeNode;
43 import org.graalvm.compiler.nodes.BeginNode;
44 import org.graalvm.compiler.nodes.ConstantNode;
45 import org.graalvm.compiler.nodes.EndNode;
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.GuardPhiNode;
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.LoopEndNode;
54 import org.graalvm.compiler.nodes.LoopExitNode;
55 import org.graalvm.compiler.nodes.MergeNode;
56 import org.graalvm.compiler.nodes.NodeView;
57 import org.graalvm.compiler.nodes.PhiNode;
58 import org.graalvm.compiler.nodes.ProxyNode;
59 import org.graalvm.compiler.nodes.SafepointNode;
60 import org.graalvm.compiler.nodes.StateSplit;
61 import org.graalvm.compiler.nodes.StructuredGraph;
62 import org.graalvm.compiler.nodes.ValueNode;
63 import org.graalvm.compiler.nodes.ValuePhiNode;
64 import org.graalvm.compiler.nodes.VirtualState.NodeClosure;
65 import org.graalvm.compiler.nodes.calc.AddNode;
66 import org.graalvm.compiler.nodes.calc.CompareNode;
67 import org.graalvm.compiler.nodes.calc.SubNode;
68 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
69 import org.graalvm.compiler.nodes.util.GraphUtil;
70
71 public class LoopFragmentInside extends LoopFragment {
72
73 /**
74 * mergedInitializers. When an inside fragment's (loop)ends are merged to create a unique exit
75 * point, some phis must be created : they phis together all the back-values of the loop-phis
76 * These can then be used to update the loop-phis' forward edge value ('initializer') in the
77 * peeling case. In the unrolling case they will be used as the value that replace the loop-phis
78 * of the duplicated inside fragment
79 */
80 private EconomicMap<PhiNode, ValueNode> mergedInitializers;
81 private final DuplicationReplacement dataFixBefore = new DuplicationReplacement() {
82
83 @Override
84 public Node replacement(Node oriInput) {
85 if (!(oriInput instanceof ValueNode)) {
86 return oriInput;
87 }
88 return prim((ValueNode) oriInput);
89 }
90 };
133 @Override
134 public void insertBefore(LoopEx loop) {
135 assert this.isDuplicate() && this.original().loop() == loop;
136
137 patchNodes(dataFixBefore);
138
139 AbstractBeginNode end = mergeEnds();
140
141 mergeEarlyExits();
142
143 original().patchPeeling(this);
144
145 AbstractBeginNode entry = getDuplicatedNode(loop.loopBegin());
146 loop.entryPoint().replaceAtPredecessor(entry);
147 end.setNext(loop.entryPoint());
148 }
149
150 /**
151 * Duplicate the body within the loop after the current copy copy of the body, updating the
152 * iteration limit to account for the duplication.
153 *
154 * @param loop
155 */
156 public void insertWithinAfter(LoopEx loop) {
157 insertWithinAfter(loop, true);
158 }
159
160 /**
161 * Duplicate the body within the loop after the current copy copy of the body.
162 *
163 * @param loop
164 * @param updateLimit true if the iteration limit should be adjusted.
165 */
166 public void insertWithinAfter(LoopEx loop, boolean updateLimit) {
167 assert isDuplicate() && original().loop() == loop;
168
169 patchNodes(dataFixWithinAfter);
170
171 /*
172 * Collect any new back edges values before updating them since they might reference each
173 * other.
174 */
175 LoopBeginNode mainLoopBegin = loop.loopBegin();
176 ArrayList<ValueNode> backedgeValues = new ArrayList<>();
177 for (PhiNode mainPhiNode : mainLoopBegin.phis()) {
178 ValueNode duplicatedNode = getDuplicatedNode(mainPhiNode.valueAt(1));
179 if (duplicatedNode == null) {
180 if (mainLoopBegin.isPhiAtMerge(mainPhiNode.valueAt(1))) {
181 duplicatedNode = ((PhiNode) (mainPhiNode.valueAt(1))).valueAt(1);
182 } else {
183 assert mainPhiNode.valueAt(1).isConstant() : mainPhiNode.valueAt(1);
184 }
185 }
186 backedgeValues.add(duplicatedNode);
187 }
188 int index = 0;
189 for (PhiNode mainPhiNode : mainLoopBegin.phis()) {
190 ValueNode duplicatedNode = backedgeValues.get(index++);
191 if (duplicatedNode != null) {
192 mainPhiNode.setValueAt(1, duplicatedNode);
193 }
194 }
195
196 placeNewSegmentAndCleanup(loop);
197
198 // Remove any safepoints from the original copy leaving only the duplicated one
199 assert loop.whole().nodes().filter(SafepointNode.class).count() == nodes().filter(SafepointNode.class).count();
200 for (SafepointNode safepoint : loop.whole().nodes().filter(SafepointNode.class)) {
201 graph().removeFixed(safepoint);
202 }
203
204 int unrollFactor = mainLoopBegin.getUnrollFactor();
205 StructuredGraph graph = mainLoopBegin.graph();
206 if (updateLimit) {
207 // Now use the previous unrollFactor to update the exit condition to power of two
208 InductionVariable iv = loop.counted().getCounter();
209 CompareNode compareNode = (CompareNode) loop.counted().getLimitTest().condition();
210 ValueNode compareBound;
211 if (compareNode.getX() == iv.valueNode()) {
212 compareBound = compareNode.getY();
213 } else if (compareNode.getY() == iv.valueNode()) {
214 compareBound = compareNode.getX();
215 } else {
216 throw GraalError.shouldNotReachHere();
217 }
218 long originalStride = unrollFactor == 1 ? iv.constantStride() : iv.constantStride() / unrollFactor;
219 if (iv.direction() == InductionVariable.Direction.Up) {
220 ConstantNode aboveVal = graph.unique(ConstantNode.forIntegerStamp(iv.initNode().stamp(NodeView.DEFAULT), unrollFactor * originalStride));
221 ValueNode newLimit = graph.addWithoutUnique(new SubNode(compareBound, aboveVal));
222 compareNode.replaceFirstInput(compareBound, newLimit);
223 } else if (iv.direction() == InductionVariable.Direction.Down) {
224 ConstantNode aboveVal = graph.unique(ConstantNode.forIntegerStamp(iv.initNode().stamp(NodeView.DEFAULT), unrollFactor * -originalStride));
225 ValueNode newLimit = graph.addWithoutUnique(new AddNode(compareBound, aboveVal));
226 compareNode.replaceFirstInput(compareBound, newLimit);
227 }
228 }
229 mainLoopBegin.setUnrollFactor(unrollFactor * 2);
230 mainLoopBegin.setLoopFrequency(mainLoopBegin.loopFrequency() / 2);
231 graph.getDebug().dump(DebugContext.DETAILED_LEVEL, graph, "LoopPartialUnroll %s", loop);
232
233 mainLoopBegin.getDebug().dump(DebugContext.VERBOSE_LEVEL, mainLoopBegin.graph(), "After insertWithinAfter %s", mainLoopBegin);
234 }
235
236 private void placeNewSegmentAndCleanup(LoopEx loop) {
237 CountedLoopInfo mainCounted = loop.counted();
238 LoopBeginNode mainLoopBegin = loop.loopBegin();
239 // Discard the segment entry and its flow, after if merging it into the loop
240 StructuredGraph graph = mainLoopBegin.graph();
241 IfNode loopTest = mainCounted.getLimitTest();
242 IfNode newSegmentTest = getDuplicatedNode(loopTest);
243 AbstractBeginNode trueSuccessor = loopTest.trueSuccessor();
244 AbstractBeginNode falseSuccessor = loopTest.falseSuccessor();
245 FixedNode firstNode;
246 boolean codeInTrueSide = false;
247 if (trueSuccessor == mainCounted.getBody()) {
248 firstNode = trueSuccessor.next();
249 codeInTrueSide = true;
|
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
24
25 package org.graalvm.compiler.loop;
26
27 import java.util.ArrayList;
28 import java.util.LinkedList;
29 import java.util.List;
30
31 import jdk.internal.vm.compiler.collections.EconomicMap;
32 import jdk.internal.vm.compiler.collections.Equivalence;
33 import org.graalvm.compiler.core.common.type.IntegerStamp;
34 import org.graalvm.compiler.debug.DebugCloseable;
35 import org.graalvm.compiler.debug.DebugContext;
36 import org.graalvm.compiler.debug.GraalError;
37 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
38 import org.graalvm.compiler.graph.Node;
39 import org.graalvm.compiler.graph.NodeBitMap;
40 import org.graalvm.compiler.graph.iterators.NodeIterable;
41 import org.graalvm.compiler.nodes.AbstractBeginNode;
42 import org.graalvm.compiler.nodes.AbstractEndNode;
43 import org.graalvm.compiler.nodes.AbstractMergeNode;
44 import org.graalvm.compiler.nodes.BeginNode;
45 import org.graalvm.compiler.nodes.ConstantNode;
46 import org.graalvm.compiler.nodes.EndNode;
47 import org.graalvm.compiler.nodes.FixedNode;
48 import org.graalvm.compiler.nodes.FixedWithNextNode;
49 import org.graalvm.compiler.nodes.FrameState;
50 import org.graalvm.compiler.nodes.GuardPhiNode;
51 import org.graalvm.compiler.nodes.IfNode;
52 import org.graalvm.compiler.nodes.LogicNode;
53 import org.graalvm.compiler.nodes.LoopBeginNode;
54 import org.graalvm.compiler.nodes.LoopEndNode;
55 import org.graalvm.compiler.nodes.LoopExitNode;
56 import org.graalvm.compiler.nodes.MergeNode;
57 import org.graalvm.compiler.nodes.NodeView;
58 import org.graalvm.compiler.nodes.PhiNode;
59 import org.graalvm.compiler.nodes.ProxyNode;
60 import org.graalvm.compiler.nodes.SafepointNode;
61 import org.graalvm.compiler.nodes.StateSplit;
62 import org.graalvm.compiler.nodes.StructuredGraph;
63 import org.graalvm.compiler.nodes.ValueNode;
64 import org.graalvm.compiler.nodes.ValuePhiNode;
65 import org.graalvm.compiler.nodes.VirtualState.NodeClosure;
66 import org.graalvm.compiler.nodes.calc.AddNode;
67 import org.graalvm.compiler.nodes.calc.CompareNode;
68 import org.graalvm.compiler.nodes.calc.ConditionalNode;
69 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
70 import org.graalvm.compiler.nodes.calc.SubNode;
71 import org.graalvm.compiler.nodes.extended.OpaqueNode;
72 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
73 import org.graalvm.compiler.nodes.util.GraphUtil;
74
75 import jdk.vm.ci.code.CodeUtil;
76
77 public class LoopFragmentInside extends LoopFragment {
78
79 /**
80 * mergedInitializers. When an inside fragment's (loop)ends are merged to create a unique exit
81 * point, some phis must be created : they phis together all the back-values of the loop-phis
82 * These can then be used to update the loop-phis' forward edge value ('initializer') in the
83 * peeling case. In the unrolling case they will be used as the value that replace the loop-phis
84 * of the duplicated inside fragment
85 */
86 private EconomicMap<PhiNode, ValueNode> mergedInitializers;
87 private final DuplicationReplacement dataFixBefore = new DuplicationReplacement() {
88
89 @Override
90 public Node replacement(Node oriInput) {
91 if (!(oriInput instanceof ValueNode)) {
92 return oriInput;
93 }
94 return prim((ValueNode) oriInput);
95 }
96 };
139 @Override
140 public void insertBefore(LoopEx loop) {
141 assert this.isDuplicate() && this.original().loop() == loop;
142
143 patchNodes(dataFixBefore);
144
145 AbstractBeginNode end = mergeEnds();
146
147 mergeEarlyExits();
148
149 original().patchPeeling(this);
150
151 AbstractBeginNode entry = getDuplicatedNode(loop.loopBegin());
152 loop.entryPoint().replaceAtPredecessor(entry);
153 end.setNext(loop.entryPoint());
154 }
155
156 /**
157 * Duplicate the body within the loop after the current copy copy of the body, updating the
158 * iteration limit to account for the duplication.
159 */
160 public void insertWithinAfter(LoopEx loop, EconomicMap<LoopBeginNode, OpaqueNode> opaqueUnrolledStrides) {
161 assert isDuplicate() && original().loop() == loop;
162
163 patchNodes(dataFixWithinAfter);
164
165 /*
166 * Collect any new back edges values before updating them since they might reference each
167 * other.
168 */
169 LoopBeginNode mainLoopBegin = loop.loopBegin();
170 ArrayList<ValueNode> backedgeValues = new ArrayList<>();
171 for (PhiNode mainPhiNode : mainLoopBegin.phis()) {
172 ValueNode duplicatedNode = getDuplicatedNode(mainPhiNode.valueAt(1));
173 if (duplicatedNode == null) {
174 if (mainLoopBegin.isPhiAtMerge(mainPhiNode.valueAt(1))) {
175 duplicatedNode = ((PhiNode) (mainPhiNode.valueAt(1))).valueAt(1);
176 } else {
177 assert mainPhiNode.valueAt(1).isConstant() : mainPhiNode.valueAt(1);
178 }
179 }
180 backedgeValues.add(duplicatedNode);
181 }
182 int index = 0;
183 for (PhiNode mainPhiNode : mainLoopBegin.phis()) {
184 ValueNode duplicatedNode = backedgeValues.get(index++);
185 if (duplicatedNode != null) {
186 mainPhiNode.setValueAt(1, duplicatedNode);
187 }
188 }
189
190 placeNewSegmentAndCleanup(loop);
191
192 // Remove any safepoints from the original copy leaving only the duplicated one
193 assert loop.whole().nodes().filter(SafepointNode.class).count() == nodes().filter(SafepointNode.class).count();
194 for (SafepointNode safepoint : loop.whole().nodes().filter(SafepointNode.class)) {
195 graph().removeFixed(safepoint);
196 }
197
198 StructuredGraph graph = mainLoopBegin.graph();
199 if (opaqueUnrolledStrides != null) {
200 OpaqueNode opaque = opaqueUnrolledStrides.get(loop.loopBegin());
201 CountedLoopInfo counted = loop.counted();
202 ValueNode counterStride = counted.getCounter().strideNode();
203 if (opaque == null) {
204 opaque = new OpaqueNode(AddNode.add(counterStride, counterStride, NodeView.DEFAULT));
205 ValueNode limit = counted.getLimit();
206 int bits = ((IntegerStamp) limit.stamp(NodeView.DEFAULT)).getBits();
207 ValueNode newLimit = SubNode.create(limit, opaque, NodeView.DEFAULT);
208 LogicNode overflowCheck;
209 ConstantNode extremum;
210 if (counted.getDirection() == InductionVariable.Direction.Up) {
211 // limit - counterStride could overflow negatively if limit - min <
212 // counterStride
213 extremum = ConstantNode.forIntegerBits(bits, CodeUtil.minValue(bits));
214 overflowCheck = IntegerBelowNode.create(SubNode.create(limit, extremum, NodeView.DEFAULT), opaque, NodeView.DEFAULT);
215 } else {
216 assert counted.getDirection() == InductionVariable.Direction.Down;
217 // limit - counterStride could overflow if max - limit < -counterStride
218 // i.e., counterStride < limit - max
219 extremum = ConstantNode.forIntegerBits(bits, CodeUtil.maxValue(bits));
220 overflowCheck = IntegerBelowNode.create(opaque, SubNode.create(limit, extremum, NodeView.DEFAULT), NodeView.DEFAULT);
221 }
222 newLimit = ConditionalNode.create(overflowCheck, extremum, newLimit, NodeView.DEFAULT);
223 CompareNode compareNode = (CompareNode) counted.getLimitTest().condition();
224 compareNode.replaceFirstInput(limit, graph.addOrUniqueWithInputs(newLimit));
225 opaqueUnrolledStrides.put(loop.loopBegin(), opaque);
226 } else {
227 assert counted.getCounter().isConstantStride();
228 assert Math.addExact(counted.getCounter().constantStride(), counted.getCounter().constantStride()) == counted.getCounter().constantStride() * 2;
229 ValueNode previousValue = opaque.getValue();
230 opaque.setValue(graph.addOrUniqueWithInputs(AddNode.add(counterStride, previousValue, NodeView.DEFAULT)));
231 GraphUtil.tryKillUnused(previousValue);
232 }
233 }
234 mainLoopBegin.setUnrollFactor(mainLoopBegin.getUnrollFactor() * 2);
235 mainLoopBegin.setLoopFrequency(mainLoopBegin.loopFrequency() / 2);
236 graph.getDebug().dump(DebugContext.DETAILED_LEVEL, graph, "LoopPartialUnroll %s", loop);
237
238 mainLoopBegin.getDebug().dump(DebugContext.VERBOSE_LEVEL, mainLoopBegin.graph(), "After insertWithinAfter %s", mainLoopBegin);
239 }
240
241 private void placeNewSegmentAndCleanup(LoopEx loop) {
242 CountedLoopInfo mainCounted = loop.counted();
243 LoopBeginNode mainLoopBegin = loop.loopBegin();
244 // Discard the segment entry and its flow, after if merging it into the loop
245 StructuredGraph graph = mainLoopBegin.graph();
246 IfNode loopTest = mainCounted.getLimitTest();
247 IfNode newSegmentTest = getDuplicatedNode(loopTest);
248 AbstractBeginNode trueSuccessor = loopTest.trueSuccessor();
249 AbstractBeginNode falseSuccessor = loopTest.falseSuccessor();
250 FixedNode firstNode;
251 boolean codeInTrueSide = false;
252 if (trueSuccessor == mainCounted.getBody()) {
253 firstNode = trueSuccessor.next();
254 codeInTrueSide = true;
|