1 package org.simantics.scl.compiler.internal.codegen.analysis;
\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.common.names.Names;
\r
6 import org.simantics.scl.compiler.constants.SCLConstant;
\r
7 import org.simantics.scl.compiler.internal.codegen.continuations.ContRef;
\r
8 import org.simantics.scl.compiler.internal.codegen.references.BoundVar;
\r
9 import org.simantics.scl.compiler.internal.codegen.references.Val;
\r
10 import org.simantics.scl.compiler.internal.codegen.references.ValRef;
\r
11 import org.simantics.scl.compiler.internal.codegen.ssa.SSABlock;
\r
12 import org.simantics.scl.compiler.internal.codegen.ssa.SSAFunction;
\r
13 import org.simantics.scl.compiler.internal.codegen.ssa.SSAStatement;
\r
14 import org.simantics.scl.compiler.internal.codegen.ssa.binders.ValRefBinder;
\r
15 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;
\r
17 import gnu.trove.map.hash.THashMap;
\r
18 import gnu.trove.set.hash.THashSet;
\r
20 public abstract class StatementBrowser {
\r
22 THashSet<SSABlock> visited;
\r
23 THashMap<SSABlock,SSAStatement> loopPos;
\r
24 SSAStatement fromStatement;
\r
27 boolean stopBrowse = false;
\r
29 protected void stopBrowse() {
\r
33 public boolean isStopped() {
\r
38 * Browses all statements that are potentially executed
\r
39 * between from and to.
\r
41 public void browseBetween(SSAStatement from, SSAStatement to) {
\r
42 SSABlock toBlock = to.getParent();
\r
43 if(from.getParent() == toBlock) {
\r
44 for(SSAStatement cur = from.getNext(); cur != to; cur = cur.getNext()) {
\r
47 visitStatement(cur);
\r
53 for(SSAStatement cur = to.getPrev(); cur != null; cur = cur.getPrev()) {
\r
54 visitStatement(cur);
\r
59 visited = new THashSet<SSABlock>();
\r
60 fromStatement = from;
\r
61 fromBlock = from.getParent();
\r
63 loopPos = new THashMap<SSABlock,SSAStatement>();
\r
64 loopPos.put(toBlock, to);
\r
66 browsePredecessors(toBlock);
\r
70 private void browseBetweenRec(SSAStatement to) {
\r
71 SSABlock toBlock = to.getParent();
\r
72 if(fromBlock == toBlock) {
\r
73 for(SSAStatement cur = fromStatement.getNext(); cur != to; cur = cur.getNext()) {
\r
76 visitStatement(cur);
\r
82 for(SSAStatement cur = to.getPrev(); cur != null; cur = cur.getPrev()) {
\r
83 visitStatement(cur);
\r
87 loopPos.put(toBlock, to);
\r
88 browsePredecessors(to.getParent());
\r
92 private void browsePredecessors(SSABlock block) {
\r
93 for(ContRef contRef = block.getOccurrence(); contRef != null; contRef = contRef.getNext()) {
\r
94 browse(contRef.getParent().getParent());
\r
100 private void browse(SSABlock block) {
\r
101 if(!visited.add(block))
\r
103 if(block == fromBlock) {
\r
104 for(SSAStatement cur = fromStatement.getNext(); cur != null; cur = cur.getNext()) {
\r
105 visitStatement(cur);
\r
111 if(loopPos.contains(block)) {
\r
112 handleLoop(block, loopPos.get(block));
\r
115 for(SSAStatement cur = block.getFirstStatement(); cur != null; cur = cur.getNext()) {
\r
116 visitStatement(cur);
\r
120 browsePredecessors(block);
\r
123 if(block.getPrev() == null) {
\r
124 SSAFunction function = block.getParent();
\r
125 if(function == fromBlock.getParent())
\r
127 Val functionTarget = function.getTarget();
\r
128 if(functionTarget instanceof BoundVar)
\r
129 browseFunction((BoundVar)functionTarget, function.getArity());
\r
135 private static void dominationError() {
\r
136 throw new InternalCompilerError("Statement 'from' does not dominate the statement 'to'.");
\r
139 protected void browseFunction(BoundVar function, int arity) {
\r
140 for(ValRef cur = function.getOccurrence(); cur != null; cur = cur.getNext()) {
\r
141 ValRefBinder binder = cur.getParent();
\r
142 if(binder instanceof LetApply)
\r
143 browseApply((LetApply)binder, cur, arity);
\r
145 unanalyzedBrowse();
\r
151 private static boolean callsOnlyOnce(Name name, int arity) {
\r
152 if(name == Names.Prelude_build)
\r
158 protected void browseApply(LetApply apply, ValRef functionRef, int arity) {
\r
159 ValRef applyFunctionRef = apply.getFunction();
\r
160 if(applyFunctionRef == functionRef) {
\r
161 if(apply.getParameters().length == arity)
\r
162 browseBetweenRec(apply);
\r
164 unanalyzedBrowse();
\r
167 Val applyFunction = applyFunctionRef.getBinding();
\r
168 if(!(applyFunction instanceof SCLConstant)) {
\r
169 unanalyzedBrowse();
\r
172 Name name = ((SCLConstant)applyFunction).getName();
\r
173 if(callsOnlyOnce(name, arity))
\r
174 browseBetweenRec(apply);
\r
176 unanalyzedBrowse();
\r
180 protected void unanalyzedBrowse() {
\r
183 protected void visitStatement(SSAStatement statement) {
\r
186 protected void handleLoop(SSABlock block, SSAStatement recursiveStatement) {
\r
187 for(SSAStatement cur = recursiveStatement; cur != null; cur = cur.getNext()) {
\r
188 visitStatement(cur);
\r
194 public boolean doesAlwaysReach() {
\r
195 for(SSABlock block : visited)
\r
196 for(SSABlock successor : block.getExit().getSuccessors())
\r
197 if(!visited.contains(successor))
\r