bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/analysis/StatementBrowser.java

   1 package org.simantics.scl.compiler.internal.codegen.analysis;
   2
   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;
  16
  17 import gnu.trove.map.hash.THashMap;
  18 import gnu.trove.set.hash.THashSet;
  19
  20 public abstract class StatementBrowser {
  21
  22     THashSet<SSABlock> visited;
  23     THashMap<SSABlock,SSAStatement> loopPos;
  24     SSAStatement fromStatement;
  25     SSABlock fromBlock;
  26
  27     boolean stopBrowse = false;
  28
  29     protected void stopBrowse() {
  30         stopBrowse = true;
  31     }
  32
  33     public boolean isStopped() {
  34         return stopBrowse;
  35     }
  36
  37     /**
  38      * Browses all statements that are potentially executed
  39      * between from and to.
  40      */
  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()) {
  45                 if(cur == null)
  46                     dominationError();
  47                 visitStatement(cur);
  48                 if(stopBrowse)
  49                     return;
  50             }
  51         }
  52         else {
  53             for(SSAStatement cur = to.getPrev(); cur != null; cur = cur.getPrev()) {
  54                 visitStatement(cur);
  55                 if(stopBrowse)
  56                     return;
  57             }
  58
  59             visited = new THashSet<SSABlock>();
  60             fromStatement = from;
  61             fromBlock = from.getParent();
  62
  63             loopPos = new THashMap<SSABlock,SSAStatement>();
  64             loopPos.put(toBlock, to);
  65
  66             browsePredecessors(toBlock);
  67         }
  68     }
  69
  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()) {
  74                 if(cur == null)
  75                     dominationError();
  76                 visitStatement(cur);
  77                 if(stopBrowse)
  78                     return;
  79             }
  80         }
  81         else {
  82             for(SSAStatement cur = to.getPrev(); cur != null; cur = cur.getPrev()) {
  83                 visitStatement(cur);
  84                 if(stopBrowse)
  85                     return;
  86             }
  87             loopPos.put(toBlock, to);
  88             browsePredecessors(to.getParent());
  89         }
  90     }
  91
  92     private void browsePredecessors(SSABlock block) {
  93         for(ContRef contRef = block.getOccurrence(); contRef != null; contRef = contRef.getNext()) {
  94             browse(contRef.getParent().getParent());
  95             if(stopBrowse)
  96                 return;
  97         }
  98     }
  99
 100     private void browse(SSABlock block) {
 101         if(!visited.add(block))
 102             return;
 103         if(block == fromBlock) {
 104             for(SSAStatement cur = fromStatement.getNext(); cur != null; cur = cur.getNext()) {
 105                 visitStatement(cur);
 106                 if(stopBrowse)
 107                     return;
 108             }
 109             return;
 110         }
 111         if(loopPos.contains(block)) {
 112             handleLoop(block, loopPos.get(block));
 113             return;
 114         }
 115         for(SSAStatement cur = block.getFirstStatement(); cur != null; cur = cur.getNext()) {
 116             visitStatement(cur);
 117             if(stopBrowse)
 118                 return;
 119         }
 120         browsePredecessors(block);
 121         if(stopBrowse)
 122             return;
 123         if(block.getPrev() == null) {
 124             SSAFunction function = block.getParent();
 125             if(function == fromBlock.getParent())
 126                 dominationError();
 127             Val functionTarget = function.getTarget();
 128             if(functionTarget instanceof BoundVar)
 129                 browseFunction((BoundVar)functionTarget, function.getArity());
 130             else
 131                 dominationError();
 132         }
 133     }
 134
 135     private static void dominationError() {
 136         throw new InternalCompilerError("Statement 'from' does not dominate the statement 'to'.");
 137     }
 138
 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);
 144             else
 145                 unanalyzedBrowse();
 146             if(stopBrowse)
 147                 return;
 148         }
 149     }
 150
 151     private static boolean callsOnlyOnce(Name name, int arity) {
 152         if(name == Names.Prelude_build)
 153             return arity == 1;
 154         else
 155             return false;
 156     }
 157
 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);
 163             else
 164                 unanalyzedBrowse();
 165         }
 166         else {
 167             Val applyFunction = applyFunctionRef.getBinding();
 168             if(!(applyFunction instanceof SCLConstant)) {
 169                 unanalyzedBrowse();
 170                 return;
 171             }
 172             Name name = ((SCLConstant)applyFunction).getName();
 173             if(callsOnlyOnce(name, arity))
 174                 browseBetweenRec(apply);
 175             else
 176                 unanalyzedBrowse();
 177         }
 178     }
 179
 180     protected void unanalyzedBrowse() {
 181     }
 182
 183     protected void visitStatement(SSAStatement statement) {
 184     }
 185
 186     protected void handleLoop(SSABlock block, SSAStatement recursiveStatement) {
 187         for(SSAStatement cur = recursiveStatement; cur != null; cur = cur.getNext()) {
 188             visitStatement(cur);
 189             if(stopBrowse)
 190                 return;
 191         }
 192     }
 193
 194     public boolean doesAlwaysReach() {
 195         for(SSABlock block : visited)
 196             for(SSABlock successor : block.getExit().getSuccessors())
 197                 if(!visited.contains(successor))
 198                     return false;
 199         return true;
 200     }
 201
 202 }