]> gerrit.simantics Code Review - simantics/platform.git/blob
e580c7c790ffb41e6a77bf6d6921c86228298668
[simantics/platform.git] /
1 package org.simantics.scl.compiler.internal.codegen.analysis;\r
2 \r
3 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;\r
4 import org.simantics.scl.compiler.common.names.Name;\r
5 import org.simantics.scl.compiler.constants.SCLConstant;\r
6 import org.simantics.scl.compiler.internal.codegen.continuations.ContRef;\r
7 import org.simantics.scl.compiler.internal.codegen.references.BoundVar;\r
8 import org.simantics.scl.compiler.internal.codegen.references.Val;\r
9 import org.simantics.scl.compiler.internal.codegen.references.ValRef;\r
10 import org.simantics.scl.compiler.internal.codegen.ssa.SSABlock;\r
11 import org.simantics.scl.compiler.internal.codegen.ssa.SSAFunction;\r
12 import org.simantics.scl.compiler.internal.codegen.ssa.SSAStatement;\r
13 import org.simantics.scl.compiler.internal.codegen.ssa.binders.ValRefBinder;\r
14 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;\r
15 \r
16 import gnu.trove.map.hash.THashMap;\r
17 import gnu.trove.set.hash.THashSet;\r
18 \r
19 public abstract class StatementBrowser {\r
20 \r
21     THashSet<SSABlock> visited;\r
22     THashMap<SSABlock,SSAStatement> loopPos;\r
23     SSAStatement fromStatement;\r
24     SSABlock fromBlock;\r
25     \r
26     boolean stopBrowse = false;\r
27     \r
28     protected void stopBrowse() {\r
29         stopBrowse = true;\r
30     }\r
31     \r
32     public boolean isStopped() {\r
33         return stopBrowse;\r
34     }\r
35     \r
36     /**\r
37      * Browses all statements that are potentially executed\r
38      * between from and to.\r
39      */\r
40     public void browseBetween(SSAStatement from, SSAStatement to) {\r
41         SSABlock toBlock = to.getParent();\r
42         if(from.getParent() == toBlock) {\r
43             for(SSAStatement cur = from.getNext(); cur != to; cur = cur.getNext()) {\r
44                 if(cur == null)\r
45                     dominationError();\r
46                 visitStatement(cur);\r
47                 if(stopBrowse)\r
48                     return;\r
49             }\r
50         }\r
51         else {\r
52             for(SSAStatement cur = to.getPrev(); cur != null; cur = cur.getPrev()) {\r
53                 visitStatement(cur);\r
54                 if(stopBrowse)\r
55                     return;\r
56             }\r
57 \r
58             visited = new THashSet<SSABlock>();            \r
59             fromStatement = from;\r
60             fromBlock = from.getParent();\r
61             \r
62             loopPos = new THashMap<SSABlock,SSAStatement>();\r
63             loopPos.put(toBlock, to);\r
64 \r
65             browsePredecessors(toBlock);            \r
66         }\r
67     }\r
68     \r
69     private void browseBetweenRec(SSAStatement to) {\r
70         SSABlock toBlock = to.getParent();\r
71         if(fromBlock == toBlock) {\r
72             for(SSAStatement cur = fromStatement.getNext(); cur != to; cur = cur.getNext()) {\r
73                 if(cur == null)\r
74                     dominationError();\r
75                 visitStatement(cur);\r
76                 if(stopBrowse)\r
77                     return;\r
78             }\r
79         }\r
80         else {\r
81             for(SSAStatement cur = to.getPrev(); cur != null; cur = cur.getPrev()) {\r
82                 visitStatement(cur);\r
83                 if(stopBrowse)\r
84                     return;\r
85             }\r
86             loopPos.put(toBlock, to);\r
87             browsePredecessors(to.getParent());            \r
88         }\r
89     }\r
90     \r
91     private void browsePredecessors(SSABlock block) {\r
92         for(ContRef contRef = block.getOccurrence(); contRef != null; contRef = contRef.getNext()) {\r
93             browse(contRef.getParent().getParent());\r
94             if(stopBrowse)\r
95                 return;\r
96         }\r
97     }    \r
98     \r
99     private void browse(SSABlock block) {\r
100         if(!visited.add(block))\r
101             return;\r
102         if(block == fromBlock) {\r
103             for(SSAStatement cur = fromStatement.getNext(); cur != null; cur = cur.getNext()) {\r
104                 visitStatement(cur);\r
105                 if(stopBrowse)\r
106                     return;\r
107             }\r
108             return;\r
109         }\r
110         if(loopPos.contains(block)) {\r
111             handleLoop(block, loopPos.get(block));\r
112             return;\r
113         }\r
114         for(SSAStatement cur = block.getFirstStatement(); cur != null; cur = cur.getNext()) {\r
115             visitStatement(cur);\r
116             if(stopBrowse)\r
117                 return;\r
118         }\r
119         browsePredecessors(block);\r
120         if(stopBrowse)\r
121             return;\r
122         if(block.getPrev() == null) {\r
123             SSAFunction function = block.getParent();\r
124             if(function == fromBlock.getParent())\r
125                 dominationError();\r
126             Val functionTarget = function.getTarget();\r
127             if(functionTarget instanceof BoundVar)\r
128                 browseFunction((BoundVar)functionTarget, function.getArity());\r
129             else\r
130                 dominationError();\r
131         }\r
132     }\r
133     \r
134     private static void dominationError() {\r
135         throw new InternalCompilerError("Statement 'from' does not dominate the statement 'to'.");\r
136     }\r
137 \r
138     protected void browseFunction(BoundVar function, int arity) {\r
139         for(ValRef cur = function.getOccurrence(); cur != null; cur = cur.getNext()) {\r
140             ValRefBinder binder = cur.getParent();\r
141             if(binder instanceof LetApply)\r
142                 browseApply((LetApply)binder, cur, arity);\r
143             else\r
144                 unanalyzedBrowse();\r
145             if(stopBrowse)\r
146                 return;\r
147         }\r
148     }\r
149     \r
150     private static final Name BUILD = Name.create("Prelude", "build");\r
151     \r
152     private static boolean callsOnlyOnce(Name name, int arity) {\r
153         if(name == BUILD)\r
154             return arity == 1;\r
155         else\r
156             return false;\r
157     }\r
158     \r
159     protected void browseApply(LetApply apply, ValRef functionRef, int arity) {\r
160         ValRef applyFunctionRef = apply.getFunction(); \r
161         if(applyFunctionRef == functionRef) {\r
162             if(apply.getParameters().length == arity)\r
163                 browseBetweenRec(apply);\r
164             else\r
165                 unanalyzedBrowse();\r
166         }\r
167         else {\r
168             Val applyFunction = applyFunctionRef.getBinding();\r
169             if(!(applyFunction instanceof SCLConstant)) {\r
170                 unanalyzedBrowse();\r
171                 return;\r
172             }\r
173             Name name = ((SCLConstant)applyFunction).getName();\r
174             if(callsOnlyOnce(name, arity))\r
175                 browseBetweenRec(apply);\r
176             else\r
177                 unanalyzedBrowse();\r
178         }\r
179     }\r
180     \r
181     protected void unanalyzedBrowse() {\r
182     }\r
183 \r
184     protected void visitStatement(SSAStatement statement) {        \r
185     }\r
186     \r
187     protected void handleLoop(SSABlock block, SSAStatement recursiveStatement) {\r
188         for(SSAStatement cur = recursiveStatement; cur != null; cur = cur.getNext()) {\r
189             visitStatement(cur);\r
190             if(stopBrowse)\r
191                 return;\r
192         }\r
193     }\r
194     \r
195     public boolean doesAlwaysReach() {\r
196         for(SSABlock block : visited)\r
197             for(SSABlock successor : block.getExit().getSuccessors())\r
198                 if(!visited.contains(successor))\r
199                     return false;\r
200         return true;\r
201     }\r
202     \r
203 }\r