X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Finternal%2Fcodegen%2Fanalysis%2FStatementBrowser.java;fp=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Finternal%2Fcodegen%2Fanalysis%2FStatementBrowser.java;h=5760890127cb89ef5a0d255f12fea785995db3f3;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/analysis/StatementBrowser.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/analysis/StatementBrowser.java
new file mode 100644
index 000000000..576089012
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/analysis/StatementBrowser.java
@@ -0,0 +1,203 @@
+package org.simantics.scl.compiler.internal.codegen.analysis;
+
+import gnu.trove.map.hash.THashMap;
+import gnu.trove.set.hash.THashSet;
+
+import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
+import org.simantics.scl.compiler.common.names.Name;
+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;
+
+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 final Name BUILD = Name.create("Prelude", "build");
+    
+    private static boolean callsOnlyOnce(Name name, int arity) {
+        if(name == 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;
+    }
+    
+}