59 import org.graalvm.compiler.nodes.ValueNode;
60 import org.graalvm.compiler.nodes.ValuePhiNode;
61 import org.graalvm.compiler.nodes.calc.AddNode;
62 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
63 import org.graalvm.compiler.nodes.calc.CompareNode;
64 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
65 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
66 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
67 import org.graalvm.compiler.nodes.calc.LeftShiftNode;
68 import org.graalvm.compiler.nodes.calc.MulNode;
69 import org.graalvm.compiler.nodes.calc.NegateNode;
70 import org.graalvm.compiler.nodes.calc.SignExtendNode;
71 import org.graalvm.compiler.nodes.calc.SubNode;
72 import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
73 import org.graalvm.compiler.nodes.cfg.Block;
74 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
75 import org.graalvm.compiler.nodes.debug.ControlFlowAnchored;
76 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
77 import org.graalvm.compiler.nodes.util.GraphUtil;
78
79 import jdk.vm.ci.code.BytecodeFrame;
80
81 public class LoopEx {
82 private final Loop<Block> loop;
83 private LoopFragmentInside inside;
84 private LoopFragmentWhole whole;
85 private CountedLoopInfo counted;
86 private LoopsData data;
87 private EconomicMap<Node, InductionVariable> ivs;
88
89 LoopEx(Loop<Block> loop, LoopsData data) {
90 this.loop = loop;
91 this.data = data;
92 }
93
94 public Loop<Block> loop() {
95 return loop;
96 }
97
98 public LoopFragmentInside inside() {
99 if (inside == null) {
100 inside = new LoopFragmentInside(this);
101 }
102 return inside;
103 }
104
105 public LoopFragmentWhole whole() {
106 if (whole == null) {
107 whole = new LoopFragmentWhole(this);
126 return null;
127 }
128
129 public boolean isOutsideLoop(Node n) {
130 return !whole().contains(n);
131 }
132
133 public LoopBeginNode loopBegin() {
134 return (LoopBeginNode) loop().getHeader().getBeginNode();
135 }
136
137 public FixedNode predecessor() {
138 return (FixedNode) loopBegin().forwardEnd().predecessor();
139 }
140
141 public FixedNode entryPoint() {
142 return loopBegin().forwardEnd();
143 }
144
145 public boolean isCounted() {
146 return counted != null;
147 }
148
149 public CountedLoopInfo counted() {
150 return counted;
151 }
152
153 public LoopEx parent() {
154 if (loop.getParent() == null) {
155 return null;
156 }
157 return data.loop(loop.getParent());
158 }
159
160 public int size() {
161 return whole().nodes().count();
162 }
163
164 @Override
165 public String toString() {
166 return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + loop().getDepth() + ") " + loopBegin();
167 }
168
169 private class InvariantPredicate implements NodePredicate {
194 }
195 ValueNode result = BinaryArithmeticNode.reassociate(binary, invariant, binary.getX(), binary.getY(), NodeView.DEFAULT);
196 if (result != binary) {
197 if (!result.isAlive()) {
198 assert !result.isDeleted();
199 result = graph.addOrUniqueWithInputs(result);
200 }
201 DebugContext debug = graph.getDebug();
202 if (debug.isLogEnabled()) {
203 debug.log("%s : Reassociated %s into %s", graph.method().format("%H::%n"), binary, result);
204 }
205 binary.replaceAtUsages(result);
206 GraphUtil.killWithUnusedFloatingInputs(binary);
207 count++;
208 }
209 }
210 return count != 0;
211 }
212
213 public boolean detectCounted() {
214 LoopBeginNode loopBegin = loopBegin();
215 FixedNode next = loopBegin.next();
216 while (next instanceof FixedGuardNode || next instanceof ValueAnchorNode || next instanceof FullInfopointNode) {
217 next = ((FixedWithNextNode) next).next();
218 }
219 if (next instanceof IfNode) {
220 IfNode ifNode = (IfNode) next;
221 boolean negated = false;
222 if (!loopBegin.isLoopExit(ifNode.falseSuccessor())) {
223 if (!loopBegin.isLoopExit(ifNode.trueSuccessor())) {
224 return false;
225 }
226 negated = true;
227 }
228 LogicNode ifTest = ifNode.condition();
229 if (!(ifTest instanceof IntegerLessThanNode) && !(ifTest instanceof IntegerEqualsNode)) {
230 if (ifTest instanceof IntegerBelowNode) {
231 ifTest.getDebug().log("Ignored potential Counted loop at %s with |<|", loopBegin);
232 }
233 return false;
234 }
235 CompareNode lessThan = (CompareNode) ifTest;
236 Condition condition = null;
237 InductionVariable iv = null;
238 ValueNode limit = null;
239 if (isOutsideLoop(lessThan.getX())) {
240 iv = getInductionVariables().get(lessThan.getY());
241 if (iv != null) {
242 condition = lessThan.condition().asCondition().mirror();
243 limit = lessThan.getX();
284 return false;
285 }
286 break;
287 case LT:
288 if (iv.direction() != Direction.Up) {
289 return false;
290 }
291 break;
292 case GE:
293 oneOff = true;
294 if (iv.direction() != Direction.Down) {
295 return false;
296 }
297 break;
298 case GT:
299 if (iv.direction() != Direction.Down) {
300 return false;
301 }
302 break;
303 default:
304 throw GraalError.shouldNotReachHere();
305 }
306 counted = new CountedLoopInfo(this, iv, ifNode, limit, oneOff, negated ? ifNode.falseSuccessor() : ifNode.trueSuccessor());
307 return true;
308 }
309 return false;
310 }
311
312 public LoopsData loopsData() {
313 return data;
314 }
315
316 public void nodesInLoopBranch(NodeBitMap branchNodes, AbstractBeginNode branch) {
317 EconomicSet<AbstractBeginNode> blocks = EconomicSet.create();
318 Collection<AbstractBeginNode> exits = new LinkedList<>();
319 Queue<Block> work = new LinkedList<>();
320 ControlFlowGraph cfg = loopsData().getCFG();
321 work.add(cfg.blockFor(branch));
322 while (!work.isEmpty()) {
323 Block b = work.remove();
324 if (loop().getExits().contains(b)) {
325 assert !exits.contains(b.getBeginNode());
326 exits.add(b.getBeginNode());
327 } else if (blocks.add(b.getBeginNode())) {
328 Block d = b.getDominatedSibling();
329 while (d != null) {
330 if (loop.getBlocks().contains(d)) {
331 work.add(d);
332 }
333 d = d.getDominatedSibling();
334 }
335 }
336 }
337 LoopFragment.computeNodes(branchNodes, branch.graph(), blocks, exits);
338 }
339
340 public EconomicMap<Node, InductionVariable> getInductionVariables() {
341 if (ivs == null) {
342 ivs = findInductionVariables(this);
343 }
344 return ivs;
448 * Deletes any nodes created within the scope of this object that have no usages.
449 */
450 public void deleteUnusedNodes() {
451 if (ivs != null) {
452 for (InductionVariable iv : ivs.getValues()) {
453 iv.deleteUnusedNodes();
454 }
455 }
456 }
457
458 /**
459 * @return true if all nodes in the loop can be duplicated.
460 */
461 public boolean canDuplicateLoop() {
462 for (Node node : inside().nodes()) {
463 if (node instanceof ControlFlowAnchored) {
464 return false;
465 }
466 if (node instanceof FrameState) {
467 FrameState frameState = (FrameState) node;
468 if (frameState.bci == BytecodeFrame.AFTER_EXCEPTION_BCI || frameState.bci == BytecodeFrame.UNWIND_BCI) {
469 return false;
470 }
471 }
472 }
473 return true;
474 }
475 }
|
59 import org.graalvm.compiler.nodes.ValueNode;
60 import org.graalvm.compiler.nodes.ValuePhiNode;
61 import org.graalvm.compiler.nodes.calc.AddNode;
62 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
63 import org.graalvm.compiler.nodes.calc.CompareNode;
64 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
65 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
66 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
67 import org.graalvm.compiler.nodes.calc.LeftShiftNode;
68 import org.graalvm.compiler.nodes.calc.MulNode;
69 import org.graalvm.compiler.nodes.calc.NegateNode;
70 import org.graalvm.compiler.nodes.calc.SignExtendNode;
71 import org.graalvm.compiler.nodes.calc.SubNode;
72 import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
73 import org.graalvm.compiler.nodes.cfg.Block;
74 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
75 import org.graalvm.compiler.nodes.debug.ControlFlowAnchored;
76 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
77 import org.graalvm.compiler.nodes.util.GraphUtil;
78
79 public class LoopEx {
80 private final Loop<Block> loop;
81 private LoopFragmentInside inside;
82 private LoopFragmentWhole whole;
83 private CountedLoopInfo counted;
84 private LoopsData data;
85 private EconomicMap<Node, InductionVariable> ivs;
86 private boolean countedLoopChecked;
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);
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 assert countedLoopChecked;
146 return counted != null;
147 }
148
149 public CountedLoopInfo counted() {
150 assert countedLoopChecked;
151 return counted;
152 }
153
154 public LoopEx parent() {
155 if (loop.getParent() == null) {
156 return null;
157 }
158 return data.loop(loop.getParent());
159 }
160
161 public int size() {
162 return whole().nodes().count();
163 }
164
165 @Override
166 public String toString() {
167 return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + loop().getDepth() + ") " + loopBegin();
168 }
169
170 private class InvariantPredicate implements NodePredicate {
195 }
196 ValueNode result = BinaryArithmeticNode.reassociate(binary, invariant, binary.getX(), binary.getY(), NodeView.DEFAULT);
197 if (result != binary) {
198 if (!result.isAlive()) {
199 assert !result.isDeleted();
200 result = graph.addOrUniqueWithInputs(result);
201 }
202 DebugContext debug = graph.getDebug();
203 if (debug.isLogEnabled()) {
204 debug.log("%s : Reassociated %s into %s", graph.method().format("%H::%n"), binary, result);
205 }
206 binary.replaceAtUsages(result);
207 GraphUtil.killWithUnusedFloatingInputs(binary);
208 count++;
209 }
210 }
211 return count != 0;
212 }
213
214 public boolean detectCounted() {
215 if (countedLoopChecked) {
216 return isCounted();
217 }
218 countedLoopChecked = true;
219 LoopBeginNode loopBegin = loopBegin();
220 FixedNode next = loopBegin.next();
221 while (next instanceof FixedGuardNode || next instanceof ValueAnchorNode || next instanceof FullInfopointNode) {
222 next = ((FixedWithNextNode) next).next();
223 }
224 if (next instanceof IfNode) {
225 IfNode ifNode = (IfNode) next;
226 boolean negated = false;
227 if (!isCfgLoopExit(ifNode.falseSuccessor())) {
228 if (!isCfgLoopExit(ifNode.trueSuccessor())) {
229 return false;
230 }
231 negated = true;
232 }
233 LogicNode ifTest = ifNode.condition();
234 if (!(ifTest instanceof IntegerLessThanNode) && !(ifTest instanceof IntegerEqualsNode)) {
235 if (ifTest instanceof IntegerBelowNode) {
236 ifTest.getDebug().log("Ignored potential Counted loop at %s with |<|", loopBegin);
237 }
238 return false;
239 }
240 CompareNode lessThan = (CompareNode) ifTest;
241 Condition condition = null;
242 InductionVariable iv = null;
243 ValueNode limit = null;
244 if (isOutsideLoop(lessThan.getX())) {
245 iv = getInductionVariables().get(lessThan.getY());
246 if (iv != null) {
247 condition = lessThan.condition().asCondition().mirror();
248 limit = lessThan.getX();
289 return false;
290 }
291 break;
292 case LT:
293 if (iv.direction() != Direction.Up) {
294 return false;
295 }
296 break;
297 case GE:
298 oneOff = true;
299 if (iv.direction() != Direction.Down) {
300 return false;
301 }
302 break;
303 case GT:
304 if (iv.direction() != Direction.Down) {
305 return false;
306 }
307 break;
308 default:
309 throw GraalError.shouldNotReachHere(condition.toString());
310 }
311 counted = new CountedLoopInfo(this, iv, ifNode, limit, oneOff, negated ? ifNode.falseSuccessor() : ifNode.trueSuccessor());
312 return true;
313 }
314 return false;
315 }
316
317 private boolean isCfgLoopExit(AbstractBeginNode begin) {
318 Block block = data.getCFG().blockFor(begin);
319 return loop.getDepth() > block.getLoopDepth() || loop.isNaturalExit(block);
320 }
321
322 public LoopsData loopsData() {
323 return data;
324 }
325
326 public void nodesInLoopBranch(NodeBitMap branchNodes, AbstractBeginNode branch) {
327 EconomicSet<AbstractBeginNode> blocks = EconomicSet.create();
328 Collection<AbstractBeginNode> exits = new LinkedList<>();
329 Queue<Block> work = new LinkedList<>();
330 ControlFlowGraph cfg = loopsData().getCFG();
331 work.add(cfg.blockFor(branch));
332 while (!work.isEmpty()) {
333 Block b = work.remove();
334 if (loop().isLoopExit(b)) {
335 assert !exits.contains(b.getBeginNode());
336 exits.add(b.getBeginNode());
337 } else if (blocks.add(b.getBeginNode())) {
338 Block d = b.getDominatedSibling();
339 while (d != null) {
340 if (loop.getBlocks().contains(d)) {
341 work.add(d);
342 }
343 d = d.getDominatedSibling();
344 }
345 }
346 }
347 LoopFragment.computeNodes(branchNodes, branch.graph(), blocks, exits);
348 }
349
350 public EconomicMap<Node, InductionVariable> getInductionVariables() {
351 if (ivs == null) {
352 ivs = findInductionVariables(this);
353 }
354 return ivs;
458 * Deletes any nodes created within the scope of this object that have no usages.
459 */
460 public void deleteUnusedNodes() {
461 if (ivs != null) {
462 for (InductionVariable iv : ivs.getValues()) {
463 iv.deleteUnusedNodes();
464 }
465 }
466 }
467
468 /**
469 * @return true if all nodes in the loop can be duplicated.
470 */
471 public boolean canDuplicateLoop() {
472 for (Node node : inside().nodes()) {
473 if (node instanceof ControlFlowAnchored) {
474 return false;
475 }
476 if (node instanceof FrameState) {
477 FrameState frameState = (FrameState) node;
478 if (frameState.isExceptionHandlingBCI()) {
479 return false;
480 }
481 }
482 }
483 return true;
484 }
485 }
|