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