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

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