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

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