--- /dev/null
+package org.simantics.scl.compiler.internal.codegen.analysis;\r
+\r
+import gnu.trove.map.hash.THashMap;\r
+import gnu.trove.set.hash.THashSet;\r
+\r
+import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;\r
+import org.simantics.scl.compiler.common.names.Name;\r
+import org.simantics.scl.compiler.constants.SCLConstant;\r
+import org.simantics.scl.compiler.internal.codegen.continuations.ContRef;\r
+import org.simantics.scl.compiler.internal.codegen.references.BoundVar;\r
+import org.simantics.scl.compiler.internal.codegen.references.Val;\r
+import org.simantics.scl.compiler.internal.codegen.references.ValRef;\r
+import org.simantics.scl.compiler.internal.codegen.ssa.SSABlock;\r
+import org.simantics.scl.compiler.internal.codegen.ssa.SSAFunction;\r
+import org.simantics.scl.compiler.internal.codegen.ssa.SSAStatement;\r
+import org.simantics.scl.compiler.internal.codegen.ssa.binders.ValRefBinder;\r
+import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;\r
+\r
+public abstract class StatementBrowser {\r
+\r
+ THashSet<SSABlock> visited;\r
+ THashMap<SSABlock,SSAStatement> loopPos;\r
+ SSAStatement fromStatement;\r
+ SSABlock fromBlock;\r
+ \r
+ boolean stopBrowse = false;\r
+ \r
+ protected void stopBrowse() {\r
+ stopBrowse = true;\r
+ }\r
+ \r
+ public boolean isStopped() {\r
+ return stopBrowse;\r
+ }\r
+ \r
+ /**\r
+ * Browses all statements that are potentially executed\r
+ * between from and to.\r
+ */\r
+ public void browseBetween(SSAStatement from, SSAStatement to) {\r
+ SSABlock toBlock = to.getParent();\r
+ if(from.getParent() == toBlock) {\r
+ for(SSAStatement cur = from.getNext(); cur != to; cur = cur.getNext()) {\r
+ if(cur == null)\r
+ dominationError();\r
+ visitStatement(cur);\r
+ if(stopBrowse)\r
+ return;\r
+ }\r
+ }\r
+ else {\r
+ for(SSAStatement cur = to.getPrev(); cur != null; cur = cur.getPrev()) {\r
+ visitStatement(cur);\r
+ if(stopBrowse)\r
+ return;\r
+ }\r
+\r
+ visited = new THashSet<SSABlock>(); \r
+ fromStatement = from;\r
+ fromBlock = from.getParent();\r
+ \r
+ loopPos = new THashMap<SSABlock,SSAStatement>();\r
+ loopPos.put(toBlock, to);\r
+\r
+ browsePredecessors(toBlock); \r
+ }\r
+ }\r
+ \r
+ private void browseBetweenRec(SSAStatement to) {\r
+ SSABlock toBlock = to.getParent();\r
+ if(fromBlock == toBlock) {\r
+ for(SSAStatement cur = fromStatement.getNext(); cur != to; cur = cur.getNext()) {\r
+ if(cur == null)\r
+ dominationError();\r
+ visitStatement(cur);\r
+ if(stopBrowse)\r
+ return;\r
+ }\r
+ }\r
+ else {\r
+ for(SSAStatement cur = to.getPrev(); cur != null; cur = cur.getPrev()) {\r
+ visitStatement(cur);\r
+ if(stopBrowse)\r
+ return;\r
+ }\r
+ loopPos.put(toBlock, to);\r
+ browsePredecessors(to.getParent()); \r
+ }\r
+ }\r
+ \r
+ private void browsePredecessors(SSABlock block) {\r
+ for(ContRef contRef = block.getOccurrence(); contRef != null; contRef = contRef.getNext()) {\r
+ browse(contRef.getParent().getParent());\r
+ if(stopBrowse)\r
+ return;\r
+ }\r
+ } \r
+ \r
+ private void browse(SSABlock block) {\r
+ if(!visited.add(block))\r
+ return;\r
+ if(block == fromBlock) {\r
+ for(SSAStatement cur = fromStatement.getNext(); cur != null; cur = cur.getNext()) {\r
+ visitStatement(cur);\r
+ if(stopBrowse)\r
+ return;\r
+ }\r
+ return;\r
+ }\r
+ if(loopPos.contains(block)) {\r
+ handleLoop(block, loopPos.get(block));\r
+ return;\r
+ }\r
+ for(SSAStatement cur = block.getFirstStatement(); cur != null; cur = cur.getNext()) {\r
+ visitStatement(cur);\r
+ if(stopBrowse)\r
+ return;\r
+ }\r
+ browsePredecessors(block);\r
+ if(stopBrowse)\r
+ return;\r
+ if(block.getPrev() == null) {\r
+ SSAFunction function = block.getParent();\r
+ if(function == fromBlock.getParent())\r
+ dominationError();\r
+ Val functionTarget = function.getTarget();\r
+ if(functionTarget instanceof BoundVar)\r
+ browseFunction((BoundVar)functionTarget, function.getArity());\r
+ else\r
+ dominationError();\r
+ }\r
+ }\r
+ \r
+ private static void dominationError() {\r
+ throw new InternalCompilerError("Statement 'from' does not dominate the statement 'to'.");\r
+ }\r
+\r
+ protected void browseFunction(BoundVar function, int arity) {\r
+ for(ValRef cur = function.getOccurrence(); cur != null; cur = cur.getNext()) {\r
+ ValRefBinder binder = cur.getParent();\r
+ if(binder instanceof LetApply)\r
+ browseApply((LetApply)binder, cur, arity);\r
+ else\r
+ unanalyzedBrowse();\r
+ if(stopBrowse)\r
+ return;\r
+ }\r
+ }\r
+ \r
+ private static final Name BUILD = Name.create("Prelude", "build");\r
+ \r
+ private static boolean callsOnlyOnce(Name name, int arity) {\r
+ if(name == BUILD)\r
+ return arity == 1;\r
+ else\r
+ return false;\r
+ }\r
+ \r
+ protected void browseApply(LetApply apply, ValRef functionRef, int arity) {\r
+ ValRef applyFunctionRef = apply.getFunction(); \r
+ if(applyFunctionRef == functionRef) {\r
+ if(apply.getParameters().length == arity)\r
+ browseBetweenRec(apply);\r
+ else\r
+ unanalyzedBrowse();\r
+ }\r
+ else {\r
+ Val applyFunction = applyFunctionRef.getBinding();\r
+ if(!(applyFunction instanceof SCLConstant)) {\r
+ unanalyzedBrowse();\r
+ return;\r
+ }\r
+ Name name = ((SCLConstant)applyFunction).getName();\r
+ if(callsOnlyOnce(name, arity))\r
+ browseBetweenRec(apply);\r
+ else\r
+ unanalyzedBrowse();\r
+ }\r
+ }\r
+ \r
+ protected void unanalyzedBrowse() {\r
+ }\r
+\r
+ protected void visitStatement(SSAStatement statement) { \r
+ }\r
+ \r
+ protected void handleLoop(SSABlock block, SSAStatement recursiveStatement) {\r
+ for(SSAStatement cur = recursiveStatement; cur != null; cur = cur.getNext()) {\r
+ visitStatement(cur);\r
+ if(stopBrowse)\r
+ return;\r
+ }\r
+ }\r
+ \r
+ public boolean doesAlwaysReach() {\r
+ for(SSABlock block : visited)\r
+ for(SSABlock successor : block.getExit().getSuccessors())\r
+ if(!visited.contains(successor))\r
+ return false;\r
+ return true;\r
+ }\r
+ \r
+}\r
Code Review / simantics / platform.git / blobdiff