44 import org.graalvm.compiler.nodes.AbstractBeginNode;
45 import org.graalvm.compiler.nodes.AbstractEndNode;
46 import org.graalvm.compiler.nodes.ConstantNode;
47 import org.graalvm.compiler.nodes.FixedGuardNode;
48 import org.graalvm.compiler.nodes.FixedNode;
49 import org.graalvm.compiler.nodes.FixedWithNextNode;
50 import org.graalvm.compiler.nodes.FrameState;
51 import org.graalvm.compiler.nodes.FullInfopointNode;
52 import org.graalvm.compiler.nodes.IfNode;
53 import org.graalvm.compiler.nodes.LogicNode;
54 import org.graalvm.compiler.nodes.LoopBeginNode;
55 import org.graalvm.compiler.nodes.NodeView;
56 import org.graalvm.compiler.nodes.PhiNode;
57 import org.graalvm.compiler.nodes.PiNode;
58 import org.graalvm.compiler.nodes.StructuredGraph;
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;
194 continue;
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();
249 }
250 } else if (isOutsideLoop(lessThan.getY())) {
251 iv = getInductionVariables().get(lessThan.getX());
252 if (iv != null) {
253 condition = lessThan.condition().asCondition();
254 limit = lessThan.getY();
255 }
256 }
257 if (condition == null) {
258 return false;
259 }
260 if (negated) {
261 condition = condition.negate();
262 }
263 boolean oneOff = false;
264 switch (condition) {
265 case EQ:
266 return false;
267 case NE: {
268 if (!iv.isConstantStride() || Math.abs(iv.constantStride()) != 1) {
269 return false;
270 }
271 IntegerStamp initStamp = (IntegerStamp) iv.initNode().stamp(NodeView.DEFAULT);
272 IntegerStamp limitStamp = (IntegerStamp) limit.stamp(NodeView.DEFAULT);
273 if (iv.direction() == Direction.Up) {
274 if (initStamp.upperBound() > limitStamp.lowerBound()) {
275 return false;
276 }
277 } else if (iv.direction() == Direction.Down) {
278 if (initStamp.lowerBound() < limitStamp.upperBound()) {
279 return false;
280 }
281 } else {
282 return false;
283 }
284 break;
285 }
286 case LE:
287 oneOff = true;
288 if (iv.direction() != Direction.Up) {
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));
|
44 import org.graalvm.compiler.nodes.AbstractBeginNode;
45 import org.graalvm.compiler.nodes.AbstractEndNode;
46 import org.graalvm.compiler.nodes.ConstantNode;
47 import org.graalvm.compiler.nodes.FixedGuardNode;
48 import org.graalvm.compiler.nodes.FixedNode;
49 import org.graalvm.compiler.nodes.FixedWithNextNode;
50 import org.graalvm.compiler.nodes.FrameState;
51 import org.graalvm.compiler.nodes.FullInfopointNode;
52 import org.graalvm.compiler.nodes.IfNode;
53 import org.graalvm.compiler.nodes.LogicNode;
54 import org.graalvm.compiler.nodes.LoopBeginNode;
55 import org.graalvm.compiler.nodes.NodeView;
56 import org.graalvm.compiler.nodes.PhiNode;
57 import org.graalvm.compiler.nodes.PiNode;
58 import org.graalvm.compiler.nodes.StructuredGraph;
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.LeftShiftNode;
65 import org.graalvm.compiler.nodes.calc.MulNode;
66 import org.graalvm.compiler.nodes.calc.NegateNode;
67 import org.graalvm.compiler.nodes.calc.SignExtendNode;
68 import org.graalvm.compiler.nodes.calc.SubNode;
69 import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
70 import org.graalvm.compiler.nodes.cfg.Block;
71 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
72 import org.graalvm.compiler.nodes.debug.ControlFlowAnchored;
73 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
74 import org.graalvm.compiler.nodes.util.GraphUtil;
75
76 public class LoopEx {
77 private final Loop<Block> loop;
78 private LoopFragmentInside inside;
79 private LoopFragmentWhole whole;
80 private CountedLoopInfo counted;
81 private LoopsData data;
82 private EconomicMap<Node, InductionVariable> ivs;
83 private boolean countedLoopChecked;
191 continue;
192 }
193 ValueNode result = BinaryArithmeticNode.reassociate(binary, invariant, binary.getX(), binary.getY(), NodeView.DEFAULT);
194 if (result != binary) {
195 if (!result.isAlive()) {
196 assert !result.isDeleted();
197 result = graph.addOrUniqueWithInputs(result);
198 }
199 DebugContext debug = graph.getDebug();
200 if (debug.isLogEnabled()) {
201 debug.log("%s : Reassociated %s into %s", graph.method().format("%H::%n"), binary, result);
202 }
203 binary.replaceAtUsages(result);
204 GraphUtil.killWithUnusedFloatingInputs(binary);
205 count++;
206 }
207 }
208 return count != 0;
209 }
210
211 @SuppressWarnings("fallthrough")
212 public boolean detectCounted() {
213 if (countedLoopChecked) {
214 return isCounted();
215 }
216 countedLoopChecked = true;
217 LoopBeginNode loopBegin = loopBegin();
218 FixedNode next = loopBegin.next();
219 while (next instanceof FixedGuardNode || next instanceof ValueAnchorNode || next instanceof FullInfopointNode) {
220 next = ((FixedWithNextNode) next).next();
221 }
222 if (next instanceof IfNode) {
223 IfNode ifNode = (IfNode) next;
224 boolean negated = false;
225 if (!isCfgLoopExit(ifNode.falseSuccessor())) {
226 if (!isCfgLoopExit(ifNode.trueSuccessor())) {
227 return false;
228 }
229 negated = true;
230 }
231 LogicNode ifTest = ifNode.condition();
232 if (!(ifTest instanceof CompareNode)) {
233 return false;
234 }
235 CompareNode compare = (CompareNode) ifTest;
236 Condition condition = null;
237 InductionVariable iv = null;
238 ValueNode limit = null;
239 if (isOutsideLoop(compare.getX())) {
240 iv = getInductionVariables().get(compare.getY());
241 if (iv != null) {
242 condition = compare.condition().asCondition().mirror();
243 limit = compare.getX();
244 }
245 } else if (isOutsideLoop(compare.getY())) {
246 iv = getInductionVariables().get(compare.getX());
247 if (iv != null) {
248 condition = compare.condition().asCondition();
249 limit = compare.getY();
250 }
251 }
252 if (condition == null) {
253 return false;
254 }
255 if (negated) {
256 condition = condition.negate();
257 }
258 boolean oneOff = false;
259 boolean unsigned = false;
260 switch (condition) {
261 case EQ:
262 if (iv.initNode() == limit) {
263 // allow "single iteration" case
264 oneOff = true;
265 } else {
266 return false;
267 }
268 break;
269 case NE: {
270 IntegerStamp initStamp = (IntegerStamp) iv.initNode().stamp(NodeView.DEFAULT);
271 IntegerStamp limitStamp = (IntegerStamp) limit.stamp(NodeView.DEFAULT);
272 IntegerStamp counterStamp = (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT);
273 if (iv.direction() == Direction.Up) {
274 if (limitStamp.asConstant() != null && limitStamp.asConstant().asLong() == counterStamp.upperBound()) {
275 // signed: i < MAX_INT
276 } else if (limitStamp.asConstant() != null && limitStamp.asConstant().asLong() == counterStamp.unsignedUpperBound()) {
277 unsigned = true;
278 } else if (!iv.isConstantStride() || Math.abs(iv.constantStride()) != 1 || initStamp.upperBound() > limitStamp.lowerBound()) {
279 return false;
280 }
281 } else if (iv.direction() == Direction.Down) {
282 if (limitStamp.asConstant() != null && limitStamp.asConstant().asLong() == counterStamp.lowerBound()) {
283 // signed: MIN_INT > i
284 } else if (limitStamp.asConstant() != null && limitStamp.asConstant().asLong() == counterStamp.unsignedLowerBound()) {
285 unsigned = true;
286 } else if (!iv.isConstantStride() || Math.abs(iv.constantStride()) != 1 || initStamp.lowerBound() < limitStamp.upperBound()) {
287 return false;
288 }
289 } else {
290 return false;
291 }
292 break;
293 }
294 case BE:
295 unsigned = true; // fall through
296 case LE:
297 oneOff = true;
298 if (iv.direction() != Direction.Up) {
299 return false;
300 }
301 break;
302 case BT:
303 unsigned = true; // fall through
304 case LT:
305 if (iv.direction() != Direction.Up) {
306 return false;
307 }
308 break;
309 case AE:
310 unsigned = true; // fall through
311 case GE:
312 oneOff = true;
313 if (iv.direction() != Direction.Down) {
314 return false;
315 }
316 break;
317 case AT:
318 unsigned = true; // fall through
319 case GT:
320 if (iv.direction() != Direction.Down) {
321 return false;
322 }
323 break;
324 default:
325 throw GraalError.shouldNotReachHere(condition.toString());
326 }
327 counted = new CountedLoopInfo(this, iv, ifNode, limit, oneOff, negated ? ifNode.falseSuccessor() : ifNode.trueSuccessor(), unsigned);
328 return true;
329 }
330 return false;
331 }
332
333 private boolean isCfgLoopExit(AbstractBeginNode begin) {
334 Block block = data.getCFG().blockFor(begin);
335 return loop.getDepth() > block.getLoopDepth() || loop.isNaturalExit(block);
336 }
337
338 public LoopsData loopsData() {
339 return data;
340 }
341
342 public void nodesInLoopBranch(NodeBitMap branchNodes, AbstractBeginNode branch) {
343 EconomicSet<AbstractBeginNode> blocks = EconomicSet.create();
344 Collection<AbstractBeginNode> exits = new LinkedList<>();
345 Queue<Block> work = new LinkedList<>();
346 ControlFlowGraph cfg = loopsData().getCFG();
347 work.add(cfg.blockFor(branch));
|