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