278 *
279 * @return {@code true} if the effects include removing the node, {@code false} otherwise.
280 */
281 protected abstract boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode);
282
283 @Override
284 protected BlockT merge(Block merge, List<BlockT> states) {
285 assert blockEffects.get(merge).isEmpty();
286 MergeProcessor processor = createMergeProcessor(merge);
287 doMergeWithoutDead(processor, states);
288 blockEffects.get(merge).addAll(processor.mergeEffects);
289 blockEffects.get(merge).addAll(processor.afterMergeEffects);
290 return processor.newState;
291 }
292
293 @Override
294 @SuppressWarnings("try")
295 protected final List<BlockT> processLoop(Loop<Block> loop, BlockT initialState) {
296 if (initialState.isDead()) {
297 ArrayList<BlockT> states = new ArrayList<>();
298 for (int i = 0; i < loop.getExits().size(); i++) {
299 states.add(initialState);
300 }
301 return states;
302 }
303 /*
304 * Special case nested loops: To avoid an exponential runtime for nested loops we try to
305 * only process them as little times as possible.
306 *
307 * In the first iteration of an outer most loop we go into the inner most loop(s). We run
308 * the first iteration of the inner most loop and then, if necessary, a second iteration.
309 *
310 * We return from the recursion and finish the first iteration of the outermost loop. If we
311 * have to do a second iteration in the outer most loop we go again into the inner most
312 * loop(s) but this time we already know all states that are killed by the loop so inside
313 * the loop we will only have those changes that propagate from the first iteration of the
314 * outer most loop into the current loop. We strip the initial loop state for the inner most
315 * loops and do the first iteration with the (possible) changes from outer loops. If there
316 * are no changes we only have to do 1 iteration and are done.
317 *
318 */
330 * This processing converges because the merge processing always makes the starting state
331 * more generic, e.g., adding phis instead of non-phi values.
332 */
333 for (int iteration = 0; iteration < 10; iteration++) {
334 try (Indent i = debug.logAndIndent("================== Process Loop Effects Closure: block:%s begin node:%s", loop.getHeader(), loop.getHeader().getBeginNode())) {
335 LoopInfo<BlockT> info = ReentrantBlockIterator.processLoop(this, loop, cloneState(lastMergedState));
336
337 List<BlockT> states = new ArrayList<>();
338 states.add(initialStateRemovedKilledLocations);
339 states.addAll(info.endStates);
340 doMergeWithoutDead(mergeProcessor, states);
341
342 debug.log("MergeProcessor New State: %s", mergeProcessor.newState);
343 debug.log("===== vs.");
344 debug.log("Last Merged State: %s", lastMergedState);
345
346 if (mergeProcessor.newState.equivalentTo(lastMergedState)) {
347 blockEffects.get(loop.getHeader()).insertAll(mergeProcessor.mergeEffects, 0);
348 loopMergeEffects.put(loop, mergeProcessor.afterMergeEffects);
349
350 assert info.exitStates.size() == loop.getExits().size();
351 loopEntryStates.put((LoopBeginNode) loop.getHeader().getBeginNode(), loopEntryState);
352 assert assertExitStatesNonEmpty(loop, info);
353
354 processKilledLoopLocations(loop, initialStateRemovedKilledLocations, mergeProcessor.newState);
355 return info.exitStates;
356 } else {
357 lastMergedState = mergeProcessor.newState;
358 for (Block block : loop.getBlocks()) {
359 blockEffects.get(block).clear();
360 }
361 }
362 }
363 }
364 throw new GraalError("too many iterations at %s", loop);
365 }
366
367 @SuppressWarnings("unused")
368 protected BlockT stripKilledLoopLocations(Loop<Block> loop, BlockT initialState) {
369 return initialState;
370 }
395 }
396 mergeProcessor.setStateIndexes(stateIndexes);
397 mergeProcessor.setNewState(getInitialState());
398 mergeProcessor.merge(states);
399 } else {
400 ArrayList<BlockT> aliveStates = new ArrayList<>(alive);
401 int[] stateIndexes = new int[alive];
402 for (int i = 0; i < states.size(); i++) {
403 if (!states.get(i).isDead()) {
404 stateIndexes[aliveStates.size()] = i;
405 aliveStates.add(states.get(i));
406 }
407 }
408 mergeProcessor.setStateIndexes(stateIndexes);
409 mergeProcessor.setNewState(getInitialState());
410 mergeProcessor.merge(aliveStates);
411 }
412 }
413
414 private boolean assertExitStatesNonEmpty(Loop<Block> loop, LoopInfo<BlockT> info) {
415 for (int i = 0; i < loop.getExits().size(); i++) {
416 assert info.exitStates.get(i) != null : "no loop exit state at " + loop.getExits().get(i) + " / " + loop.getHeader();
417 }
418 return true;
419 }
420
421 protected abstract void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects);
422
423 protected abstract MergeProcessor createMergeProcessor(Block merge);
424
425 /**
426 * The main workhorse for merging states, both for loops and for normal merges.
427 */
428 protected abstract class MergeProcessor {
429
430 private final Block mergeBlock;
431 private final AbstractMergeNode merge;
432
433 protected final GraphEffectList mergeEffects;
434 protected final GraphEffectList afterMergeEffects;
435
436 /**
|
278 *
279 * @return {@code true} if the effects include removing the node, {@code false} otherwise.
280 */
281 protected abstract boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode);
282
283 @Override
284 protected BlockT merge(Block merge, List<BlockT> states) {
285 assert blockEffects.get(merge).isEmpty();
286 MergeProcessor processor = createMergeProcessor(merge);
287 doMergeWithoutDead(processor, states);
288 blockEffects.get(merge).addAll(processor.mergeEffects);
289 blockEffects.get(merge).addAll(processor.afterMergeEffects);
290 return processor.newState;
291 }
292
293 @Override
294 @SuppressWarnings("try")
295 protected final List<BlockT> processLoop(Loop<Block> loop, BlockT initialState) {
296 if (initialState.isDead()) {
297 ArrayList<BlockT> states = new ArrayList<>();
298 for (int i = 0; i < loop.getLoopExits().size(); i++) {
299 states.add(initialState);
300 }
301 return states;
302 }
303 /*
304 * Special case nested loops: To avoid an exponential runtime for nested loops we try to
305 * only process them as little times as possible.
306 *
307 * In the first iteration of an outer most loop we go into the inner most loop(s). We run
308 * the first iteration of the inner most loop and then, if necessary, a second iteration.
309 *
310 * We return from the recursion and finish the first iteration of the outermost loop. If we
311 * have to do a second iteration in the outer most loop we go again into the inner most
312 * loop(s) but this time we already know all states that are killed by the loop so inside
313 * the loop we will only have those changes that propagate from the first iteration of the
314 * outer most loop into the current loop. We strip the initial loop state for the inner most
315 * loops and do the first iteration with the (possible) changes from outer loops. If there
316 * are no changes we only have to do 1 iteration and are done.
317 *
318 */
330 * This processing converges because the merge processing always makes the starting state
331 * more generic, e.g., adding phis instead of non-phi values.
332 */
333 for (int iteration = 0; iteration < 10; iteration++) {
334 try (Indent i = debug.logAndIndent("================== Process Loop Effects Closure: block:%s begin node:%s", loop.getHeader(), loop.getHeader().getBeginNode())) {
335 LoopInfo<BlockT> info = ReentrantBlockIterator.processLoop(this, loop, cloneState(lastMergedState));
336
337 List<BlockT> states = new ArrayList<>();
338 states.add(initialStateRemovedKilledLocations);
339 states.addAll(info.endStates);
340 doMergeWithoutDead(mergeProcessor, states);
341
342 debug.log("MergeProcessor New State: %s", mergeProcessor.newState);
343 debug.log("===== vs.");
344 debug.log("Last Merged State: %s", lastMergedState);
345
346 if (mergeProcessor.newState.equivalentTo(lastMergedState)) {
347 blockEffects.get(loop.getHeader()).insertAll(mergeProcessor.mergeEffects, 0);
348 loopMergeEffects.put(loop, mergeProcessor.afterMergeEffects);
349
350 assert info.exitStates.size() == loop.getLoopExits().size();
351 loopEntryStates.put((LoopBeginNode) loop.getHeader().getBeginNode(), loopEntryState);
352 assert assertExitStatesNonEmpty(loop, info);
353
354 processKilledLoopLocations(loop, initialStateRemovedKilledLocations, mergeProcessor.newState);
355 return info.exitStates;
356 } else {
357 lastMergedState = mergeProcessor.newState;
358 for (Block block : loop.getBlocks()) {
359 blockEffects.get(block).clear();
360 }
361 }
362 }
363 }
364 throw new GraalError("too many iterations at %s", loop);
365 }
366
367 @SuppressWarnings("unused")
368 protected BlockT stripKilledLoopLocations(Loop<Block> loop, BlockT initialState) {
369 return initialState;
370 }
395 }
396 mergeProcessor.setStateIndexes(stateIndexes);
397 mergeProcessor.setNewState(getInitialState());
398 mergeProcessor.merge(states);
399 } else {
400 ArrayList<BlockT> aliveStates = new ArrayList<>(alive);
401 int[] stateIndexes = new int[alive];
402 for (int i = 0; i < states.size(); i++) {
403 if (!states.get(i).isDead()) {
404 stateIndexes[aliveStates.size()] = i;
405 aliveStates.add(states.get(i));
406 }
407 }
408 mergeProcessor.setStateIndexes(stateIndexes);
409 mergeProcessor.setNewState(getInitialState());
410 mergeProcessor.merge(aliveStates);
411 }
412 }
413
414 private boolean assertExitStatesNonEmpty(Loop<Block> loop, LoopInfo<BlockT> info) {
415 for (int i = 0; i < loop.getLoopExits().size(); i++) {
416 assert info.exitStates.get(i) != null : "no loop exit state at " + loop.getLoopExits().get(i) + " / " + loop.getHeader();
417 }
418 return true;
419 }
420
421 protected abstract void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects);
422
423 protected abstract MergeProcessor createMergeProcessor(Block merge);
424
425 /**
426 * The main workhorse for merging states, both for loops and for normal merges.
427 */
428 protected abstract class MergeProcessor {
429
430 private final Block mergeBlock;
431 private final AbstractMergeNode merge;
432
433 protected final GraphEffectList mergeEffects;
434 protected final GraphEffectList afterMergeEffects;
435
436 /**
|