1 package org.simantics.scl.compiler.internal.codegen.analysis;
\r
3 import org.simantics.scl.compiler.common.names.Name;
\r
4 import org.simantics.scl.compiler.common.names.Names;
\r
5 import org.simantics.scl.compiler.constants.SCLConstant;
\r
6 import org.simantics.scl.compiler.internal.codegen.references.Val;
\r
7 import org.simantics.scl.compiler.internal.codegen.references.ValRef;
\r
8 import org.simantics.scl.compiler.internal.codegen.ssa.SSABlock;
\r
9 import org.simantics.scl.compiler.internal.codegen.ssa.SSAFunction;
\r
10 import org.simantics.scl.compiler.internal.codegen.ssa.binders.ValRefBinder;
\r
11 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;
\r
13 import gnu.trove.set.hash.THashSet;
\r
15 public class LoopAnalysis {
\r
18 * Checks if it is possible to return to the loop after exiting
\r
19 * before exiting the function where the block belongs to.
\r
21 private static boolean isLoopingBlock(SSABlock block) {
\r
22 THashSet<SSABlock> handled = new THashSet<SSABlock>();
\r
23 for(SSABlock succBlock : block.getExit().getSuccessors())
\r
24 if(isLoopingBlock(block, handled, succBlock))
\r
30 * Checks if it is possible to execute block more than once without visiting
\r
31 * the breaker block. It is assumed that breaker is a dominator of the block.
\r
33 public static boolean isLoopingBlockWithBreaker(SSABlock block, SSABlock breaker) {
\r
34 SSAFunction function = block.getParent();
\r
36 if(function == block.getParent()) {
\r
37 THashSet<SSABlock> handled = new THashSet<SSABlock>();
\r
38 handled.add(breaker);
\r
39 for(SSABlock succBlock : block.getExit().getSuccessors())
\r
40 if(isLoopingBlock(block, handled, succBlock))
\r
45 if(isLoopingBlock(block))
\r
47 Val functionTarget = function.getTarget();
\r
48 if(functionTarget.hasMoreThanOneOccurences())
\r
50 ValRef occ = functionTarget.getOccurrence();
\r
53 ValRefBinder occParent = occ.getParent();
\r
54 if(!(occParent instanceof LetApply))
\r
55 return true; // Not necessarily the right answer, but we don't try to analyse further
\r
56 LetApply apply = (LetApply)occParent;
\r
57 if(!isAppliedAtMostOnce(apply, occ, function))
\r
59 return isLoopingBlockWithBreaker(apply.getParent(), breaker);
\r
63 private static boolean isAppliedAtMostOnce(LetApply apply, ValRef funRef, SSAFunction function) {
\r
64 ValRef applyFunctionRef = apply.getFunction();
\r
65 if(funRef == applyFunctionRef) {
\r
66 return apply.getParameters().length == function.getArity();
\r
68 Val applyFunction = applyFunctionRef.getBinding();
\r
69 if(!(applyFunction instanceof SCLConstant))
\r
70 return false; // Not necessarily the right answer
\r
71 Name name = ((SCLConstant)applyFunction).getName();
\r
72 if(name == Names.Prelude_build)
\r
77 private static boolean isLoopingBlock(SSABlock originalBlock,
\r
78 THashSet<SSABlock> handled, SSABlock block) {
\r
79 if(!handled.add(block))
\r
81 if(block == originalBlock)
\r
83 for(SSABlock succBlock : block.getExit().getSuccessors())
\r
84 if(isLoopingBlock(originalBlock, handled, succBlock))
\r