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