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.DebugContext;
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.PhiNode;
50 import org.graalvm.compiler.nodes.PiNode;
51 import org.graalvm.compiler.nodes.StructuredGraph;
52 import org.graalvm.compiler.nodes.ValueNode;
53 import org.graalvm.compiler.nodes.ValuePhiNode;
55 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
56 import org.graalvm.compiler.nodes.calc.CompareNode;
57 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
58 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
59 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
60 import org.graalvm.compiler.nodes.calc.LeftShiftNode;
61 import org.graalvm.compiler.nodes.calc.MulNode;
62 import org.graalvm.compiler.nodes.calc.NegateNode;
63 import org.graalvm.compiler.nodes.calc.SignExtendNode;
64 import org.graalvm.compiler.nodes.calc.SubNode;
65 import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
66 import org.graalvm.compiler.nodes.cfg.Block;
67 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
68 import org.graalvm.compiler.nodes.debug.ControlFlowAnchored;
69 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
70 import org.graalvm.compiler.nodes.util.GraphUtil;
71 import org.graalvm.util.EconomicMap;
72 import org.graalvm.util.EconomicSet;
73 import org.graalvm.util.Equivalence;
74
75 import jdk.vm.ci.code.BytecodeFrame;
76
77 public class LoopEx {
78 private final Loop<Block> loop;
79 private LoopFragmentInside inside;
80 private LoopFragmentWhole whole;
81 private CountedLoopInfo counted;
82 private LoopsData data;
83 private EconomicMap<Node, InductionVariable> ivs;
84
85 LoopEx(Loop<Block> loop, LoopsData data) {
86 this.loop = loop;
87 this.data = data;
88 }
89
90 public Loop<Block> loop() {
91 return loop;
92 }
93
94 public LoopFragmentInside inside() {
95 if (inside == null) {
147 }
148
149 public LoopEx parent() {
150 if (loop.getParent() == null) {
151 return null;
152 }
153 return data.loop(loop.getParent());
154 }
155
156 public int size() {
157 return whole().nodes().count();
158 }
159
160 @Override
161 public String toString() {
162 return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + loop().getDepth() + ") " + loopBegin();
163 }
164
165 private class InvariantPredicate implements NodePredicate {
166
167 @Override
168 public boolean apply(Node n) {
169 return isOutsideLoop(n);
170 }
171 }
172
173 public void reassociateInvariants() {
174 InvariantPredicate invariant = new InvariantPredicate();
175 StructuredGraph graph = loopBegin().graph();
176 for (BinaryArithmeticNode<?> binary : whole().nodes().filter(BinaryArithmeticNode.class)) {
177 if (!binary.isAssociative()) {
178 continue;
179 }
180 ValueNode result = BinaryArithmeticNode.reassociate(binary, invariant, binary.getX(), binary.getY());
181 if (result != binary) {
182 DebugContext debug = graph.getDebug();
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) {
|
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 jdk.vm.ci.code.BytecodeFrame;
26 import org.graalvm.compiler.core.common.calc.Condition;
27 import org.graalvm.compiler.core.common.cfg.Loop;
28 import org.graalvm.compiler.core.common.type.IntegerStamp;
29 import org.graalvm.compiler.debug.DebugContext;
30 import org.graalvm.compiler.debug.GraalError;
31 import org.graalvm.compiler.graph.Graph;
32 import org.graalvm.compiler.graph.Node;
33 import org.graalvm.compiler.graph.NodeBitMap;
34 import org.graalvm.compiler.graph.iterators.NodePredicate;
35 import org.graalvm.compiler.loop.InductionVariable.Direction;
36 import org.graalvm.compiler.nodes.AbstractBeginNode;
37 import org.graalvm.compiler.nodes.AbstractEndNode;
38 import org.graalvm.compiler.nodes.ConstantNode;
39 import org.graalvm.compiler.nodes.FixedGuardNode;
40 import org.graalvm.compiler.nodes.FixedNode;
41 import org.graalvm.compiler.nodes.FixedWithNextNode;
42 import org.graalvm.compiler.nodes.FrameState;
43 import org.graalvm.compiler.nodes.FullInfopointNode;
44 import org.graalvm.compiler.nodes.IfNode;
45 import org.graalvm.compiler.nodes.LogicNode;
46 import org.graalvm.compiler.nodes.LoopBeginNode;
47 import org.graalvm.compiler.nodes.PhiNode;
48 import org.graalvm.compiler.nodes.PiNode;
49 import org.graalvm.compiler.nodes.StructuredGraph;
50 import org.graalvm.compiler.nodes.ValueNode;
51 import org.graalvm.compiler.nodes.ValuePhiNode;
53 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
54 import org.graalvm.compiler.nodes.calc.CompareNode;
55 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
56 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
57 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
58 import org.graalvm.compiler.nodes.calc.LeftShiftNode;
59 import org.graalvm.compiler.nodes.calc.MulNode;
60 import org.graalvm.compiler.nodes.calc.NegateNode;
61 import org.graalvm.compiler.nodes.calc.SignExtendNode;
62 import org.graalvm.compiler.nodes.calc.SubNode;
63 import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
64 import org.graalvm.compiler.nodes.cfg.Block;
65 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
66 import org.graalvm.compiler.nodes.debug.ControlFlowAnchored;
67 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
68 import org.graalvm.compiler.nodes.util.GraphUtil;
69 import org.graalvm.util.EconomicMap;
70 import org.graalvm.util.EconomicSet;
71 import org.graalvm.util.Equivalence;
72
73 import java.util.Collection;
74 import java.util.LinkedList;
75 import java.util.Queue;
76
77 public class LoopEx {
78 private final Loop<Block> loop;
79 private LoopFragmentInside inside;
80 private LoopFragmentWhole whole;
81 private CountedLoopInfo counted;
82 private LoopsData data;
83 private EconomicMap<Node, InductionVariable> ivs;
84
85 LoopEx(Loop<Block> loop, LoopsData data) {
86 this.loop = loop;
87 this.data = data;
88 }
89
90 public Loop<Block> loop() {
91 return loop;
92 }
93
94 public LoopFragmentInside inside() {
95 if (inside == null) {
147 }
148
149 public LoopEx parent() {
150 if (loop.getParent() == null) {
151 return null;
152 }
153 return data.loop(loop.getParent());
154 }
155
156 public int size() {
157 return whole().nodes().count();
158 }
159
160 @Override
161 public String toString() {
162 return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + loop().getDepth() + ") " + loopBegin();
163 }
164
165 private class InvariantPredicate implements NodePredicate {
166
167 private final Graph.Mark mark;
168
169 InvariantPredicate() {
170 this.mark = loopBegin().graph().getMark();
171 }
172
173 @Override
174 public boolean apply(Node n) {
175 if (loopBegin().graph().isNew(mark, n)) {
176 // Newly created nodes are unknown.
177 return false;
178 }
179 return isOutsideLoop(n);
180 }
181 }
182
183 public boolean reassociateInvariants() {
184 int count = 0;
185 StructuredGraph graph = loopBegin().graph();
186 InvariantPredicate invariant = new InvariantPredicate();
187 for (BinaryArithmeticNode<?> binary : whole().nodes().filter(BinaryArithmeticNode.class)) {
188 if (!binary.isAssociative()) {
189 continue;
190 }
191 ValueNode result = BinaryArithmeticNode.reassociate(binary, invariant, binary.getX(), binary.getY());
192 if (result != binary) {
193 if (!result.isAlive()) {
194 assert !result.isDeleted();
195 result = graph.addOrUniqueWithInputs(result);
196 }
197 DebugContext debug = graph.getDebug();
198 if (debug.isLogEnabled()) {
199 debug.log("%s : Reassociated %s into %s", graph.method().format("%H::%n"), binary, result);
200 }
201 binary.replaceAtUsages(result);
202 GraphUtil.killWithUnusedFloatingInputs(binary);
203 count++;
204 }
205 }
206 return count != 0;
207 }
208
209 public boolean detectCounted() {
210 LoopBeginNode loopBegin = loopBegin();
211 FixedNode next = loopBegin.next();
212 while (next instanceof FixedGuardNode || next instanceof ValueAnchorNode || next instanceof FullInfopointNode) {
213 next = ((FixedWithNextNode) next).next();
214 }
215 if (next instanceof IfNode) {
216 IfNode ifNode = (IfNode) next;
217 boolean negated = false;
218 if (!loopBegin.isLoopExit(ifNode.falseSuccessor())) {
219 if (!loopBegin.isLoopExit(ifNode.trueSuccessor())) {
220 return false;
221 }
222 negated = true;
223 }
224 LogicNode ifTest = ifNode.condition();
225 if (!(ifTest instanceof IntegerLessThanNode) && !(ifTest instanceof IntegerEqualsNode)) {
226 if (ifTest instanceof IntegerBelowNode) {
|