]> gerrit.simantics Code Review - simantics/platform.git/blob
9d6a5645ac1b52cd8bff29da183ea7b9bdb30d35
[simantics/platform.git] /
1 package org.simantics.scl.compiler.internal.codegen.analysis;\r
2 \r
3 import gnu.trove.set.hash.THashSet;\r
4 \r
5 import org.simantics.scl.compiler.common.names.Name;\r
6 import org.simantics.scl.compiler.constants.SCLConstant;\r
7 import org.simantics.scl.compiler.internal.codegen.references.Val;\r
8 import org.simantics.scl.compiler.internal.codegen.references.ValRef;\r
9 import org.simantics.scl.compiler.internal.codegen.ssa.SSABlock;\r
10 import org.simantics.scl.compiler.internal.codegen.ssa.SSAFunction;\r
11 import org.simantics.scl.compiler.internal.codegen.ssa.binders.ValRefBinder;\r
12 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;\r
13 \r
14 public class LoopAnalysis {\r
15 \r
16     /**\r
17      * Checks if it is possible to return to the loop after exiting \r
18      * before exiting the function where the block belongs to.\r
19      */\r
20     private static boolean isLoopingBlock(SSABlock block) {\r
21         THashSet<SSABlock> handled = new THashSet<SSABlock>();\r
22         for(SSABlock succBlock : block.getExit().getSuccessors())\r
23             if(isLoopingBlock(block, handled, succBlock))\r
24                 return true;\r
25         return false;\r
26     }\r
27 \r
28     /**\r
29      * Checks if it is possible to execute block more than once without visiting\r
30      * the breaker block. It is assumed that breaker is a dominator of the block.\r
31      */\r
32     public static boolean isLoopingBlockWithBreaker(SSABlock block, SSABlock breaker) {\r
33         SSAFunction function = block.getParent();\r
34         \r
35         if(function == block.getParent()) {            \r
36             THashSet<SSABlock> handled = new THashSet<SSABlock>();\r
37             handled.add(breaker);\r
38             for(SSABlock succBlock : block.getExit().getSuccessors())\r
39                 if(isLoopingBlock(block, handled, succBlock))\r
40                     return true;\r
41             return false;\r
42         }\r
43         else {\r
44             if(isLoopingBlock(block))\r
45                 return false;\r
46             Val functionTarget = function.getTarget();\r
47             if(functionTarget.hasMoreThanOneOccurences())\r
48                 return false;\r
49             ValRef occ = functionTarget.getOccurrence();\r
50             if(occ == null)\r
51                 return false;\r
52             ValRefBinder occParent = occ.getParent();\r
53             if(!(occParent instanceof LetApply))\r
54                 return true; // Not necessarily the right answer, but we don't try to analyse further\r
55             LetApply apply = (LetApply)occParent;\r
56             if(!isAppliedAtMostOnce(apply, occ, function))\r
57                 return true;\r
58             return isLoopingBlockWithBreaker(apply.getParent(), breaker);\r
59         }\r
60     }    \r
61 \r
62     private static final Name BUILD = Name.create("Prelude", "build");\r
63     \r
64     private static boolean isAppliedAtMostOnce(LetApply apply, ValRef funRef, SSAFunction function) {\r
65         ValRef applyFunctionRef = apply.getFunction();\r
66         if(funRef == applyFunctionRef) {            \r
67             return apply.getParameters().length == function.getArity();\r
68         }\r
69         Val applyFunction = applyFunctionRef.getBinding();\r
70         if(!(applyFunction instanceof SCLConstant))\r
71             return false; // Not necessarily the right answer\r
72         Name name = ((SCLConstant)applyFunction).getName();\r
73         if(name == BUILD)\r
74             return true;\r
75         return false;\r
76     }\r
77 \r
78     private static boolean isLoopingBlock(SSABlock originalBlock,\r
79             THashSet<SSABlock> handled, SSABlock block) {\r
80         if(!handled.add(block))\r
81             return false;\r
82         if(block == originalBlock)\r
83             return true;\r
84         for(SSABlock succBlock : block.getExit().getSuccessors())\r
85             if(isLoopingBlock(originalBlock, handled, succBlock))\r
86                 return true;\r
87         return false;\r
88     }\r
89     \r
90 }\r