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

   1 package org.simantics.scl.compiler.internal.codegen.analysis;\r
   2 \r
   3 import gnu.trove.set.hash.THashSet;\r
   4 \r
   5 import org.simantics.scl.compiler.common.names.Name;\r
   6 import org.simantics.scl.compiler.constants.SCLConstant;\r
   7 import org.simantics.scl.compiler.internal.codegen.references.Val;\r
   8 import org.simantics.scl.compiler.internal.codegen.references.ValRef;\r
   9 import org.simantics.scl.compiler.internal.codegen.ssa.SSABlock;\r
  10 import org.simantics.scl.compiler.internal.codegen.ssa.SSAFunction;\r
  11 import org.simantics.scl.compiler.internal.codegen.ssa.binders.ValRefBinder;\r
  12 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;\r
  13 \r
  14 public class LoopAnalysis {\r
  15 \r
  16     /**\r
  17      * Checks if it is possible to return to the loop after exiting \r
  18      * before exiting the function where the block belongs to.\r
  19      */\r
  20     private static boolean isLoopingBlock(SSABlock block) {\r
  21         THashSet<SSABlock> handled = new THashSet<SSABlock>();\r
  22         for(SSABlock succBlock : block.getExit().getSuccessors())\r
  23             if(isLoopingBlock(block, handled, succBlock))\r
  24                 return true;\r
  25         return false;\r
  26     }\r
  27 \r
  28     /**\r
  29      * Checks if it is possible to execute block more than once without visiting\r
  30      * the breaker block. It is assumed that breaker is a dominator of the block.\r
  31      */\r
  32     public static boolean isLoopingBlockWithBreaker(SSABlock block, SSABlock breaker) {\r
  33         SSAFunction function = block.getParent();\r
  34         \r
  35         if(function == block.getParent()) {            \r
  36             THashSet<SSABlock> handled = new THashSet<SSABlock>();\r
  37             handled.add(breaker);\r
  38             for(SSABlock succBlock : block.getExit().getSuccessors())\r
  39                 if(isLoopingBlock(block, handled, succBlock))\r
  40                     return true;\r
  41             return false;\r
  42         }\r
  43         else {\r
  44             if(isLoopingBlock(block))\r
  45                 return false;\r
  46             Val functionTarget = function.getTarget();\r
  47             if(functionTarget.hasMoreThanOneOccurences())\r
  48                 return false;\r
  49             ValRef occ = functionTarget.getOccurrence();\r
  50             if(occ == null)\r
  51                 return false;\r
  52             ValRefBinder occParent = occ.getParent();\r
  53             if(!(occParent instanceof LetApply))\r
  54                 return true; // Not necessarily the right answer, but we don't try to analyse further\r
  55             LetApply apply = (LetApply)occParent;\r
  56             if(!isAppliedAtMostOnce(apply, occ, function))\r
  57                 return true;\r
  58             return isLoopingBlockWithBreaker(apply.getParent(), breaker);\r
  59         }\r
  60     }    \r
  61 \r
  62     private static final Name BUILD = Name.create("Prelude", "build");\r
  63     \r
  64     private static boolean isAppliedAtMostOnce(LetApply apply, ValRef funRef, SSAFunction function) {\r
  65         ValRef applyFunctionRef = apply.getFunction();\r
  66         if(funRef == applyFunctionRef) {            \r
  67             return apply.getParameters().length == function.getArity();\r
  68         }\r
  69         Val applyFunction = applyFunctionRef.getBinding();\r
  70         if(!(applyFunction instanceof SCLConstant))\r
  71             return false; // Not necessarily the right answer\r
  72         Name name = ((SCLConstant)applyFunction).getName();\r
  73         if(name == BUILD)\r
  74             return true;\r
  75         return false;\r
  76     }\r
  77 \r
  78     private static boolean isLoopingBlock(SSABlock originalBlock,\r
  79             THashSet<SSABlock> handled, SSABlock block) {\r
  80         if(!handled.add(block))\r
  81             return false;\r
  82         if(block == originalBlock)\r
  83             return true;\r
  84         for(SSABlock succBlock : block.getExit().getSuccessors())\r
  85             if(isLoopingBlock(originalBlock, handled, succBlock))\r
  86                 return true;\r
  87         return false;\r
  88     }\r
  89     \r
  90 }\r