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