1 package org.simantics.scl.compiler.internal.codegen.analysis;
\r
3 import gnu.trove.map.hash.THashMap;
\r
4 import gnu.trove.set.hash.THashSet;
\r
6 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
\r
7 import org.simantics.scl.compiler.common.names.Name;
\r
8 import org.simantics.scl.compiler.constants.SCLConstant;
\r
9 import org.simantics.scl.compiler.internal.codegen.continuations.ContRef;
\r
10 import org.simantics.scl.compiler.internal.codegen.references.BoundVar;
\r
11 import org.simantics.scl.compiler.internal.codegen.references.Val;
\r
12 import org.simantics.scl.compiler.internal.codegen.references.ValRef;
\r
13 import org.simantics.scl.compiler.internal.codegen.ssa.SSABlock;
\r
14 import org.simantics.scl.compiler.internal.codegen.ssa.SSAFunction;
\r
15 import org.simantics.scl.compiler.internal.codegen.ssa.SSAStatement;
\r
16 import org.simantics.scl.compiler.internal.codegen.ssa.binders.ValRefBinder;
\r
17 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;
\r
19 public abstract class StatementBrowser {
\r
21 THashSet<SSABlock> visited;
\r
22 THashMap<SSABlock,SSAStatement> loopPos;
\r
23 SSAStatement fromStatement;
\r
26 boolean stopBrowse = false;
\r
28 protected void stopBrowse() {
\r
32 public boolean isStopped() {
\r
37 * Browses all statements that are potentially executed
\r
38 * between from and to.
\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
46 visitStatement(cur);
\r
52 for(SSAStatement cur = to.getPrev(); cur != null; cur = cur.getPrev()) {
\r
53 visitStatement(cur);
\r
58 visited = new THashSet<SSABlock>();
\r
59 fromStatement = from;
\r
60 fromBlock = from.getParent();
\r
62 loopPos = new THashMap<SSABlock,SSAStatement>();
\r
63 loopPos.put(toBlock, to);
\r
65 browsePredecessors(toBlock);
\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
75 visitStatement(cur);
\r
81 for(SSAStatement cur = to.getPrev(); cur != null; cur = cur.getPrev()) {
\r
82 visitStatement(cur);
\r
86 loopPos.put(toBlock, to);
\r
87 browsePredecessors(to.getParent());
\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
99 private void browse(SSABlock block) {
\r
100 if(!visited.add(block))
\r
102 if(block == fromBlock) {
\r
103 for(SSAStatement cur = fromStatement.getNext(); cur != null; cur = cur.getNext()) {
\r
104 visitStatement(cur);
\r
110 if(loopPos.contains(block)) {
\r
111 handleLoop(block, loopPos.get(block));
\r
114 for(SSAStatement cur = block.getFirstStatement(); cur != null; cur = cur.getNext()) {
\r
115 visitStatement(cur);
\r
119 browsePredecessors(block);
\r
122 if(block.getPrev() == null) {
\r
123 SSAFunction function = block.getParent();
\r
124 if(function == fromBlock.getParent())
\r
126 Val functionTarget = function.getTarget();
\r
127 if(functionTarget instanceof BoundVar)
\r
128 browseFunction((BoundVar)functionTarget, function.getArity());
\r
134 private static void dominationError() {
\r
135 throw new InternalCompilerError("Statement 'from' does not dominate the statement 'to'.");
\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
144 unanalyzedBrowse();
\r
150 private static final Name BUILD = Name.create("Prelude", "build");
\r
152 private static boolean callsOnlyOnce(Name name, int arity) {
\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
165 unanalyzedBrowse();
\r
168 Val applyFunction = applyFunctionRef.getBinding();
\r
169 if(!(applyFunction instanceof SCLConstant)) {
\r
170 unanalyzedBrowse();
\r
173 Name name = ((SCLConstant)applyFunction).getName();
\r
174 if(callsOnlyOnce(name, arity))
\r
175 browseBetweenRec(apply);
\r
177 unanalyzedBrowse();
\r
181 protected void unanalyzedBrowse() {
\r
184 protected void visitStatement(SSAStatement statement) {
\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
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