bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/SSABlock.java

   1 package org.simantics.scl.compiler.internal.codegen.ssa;\r
   2 \r
   3 import java.util.ArrayList;\r
   4 \r
   5 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;\r
   6 import org.simantics.scl.compiler.constants.Constant;\r
   7 import org.simantics.scl.compiler.constants.SCLConstant;\r
   8 import org.simantics.scl.compiler.internal.codegen.continuations.BranchRef;\r
   9 import org.simantics.scl.compiler.internal.codegen.continuations.Cont;\r
  10 import org.simantics.scl.compiler.internal.codegen.continuations.ContRef;\r
  11 import org.simantics.scl.compiler.internal.codegen.references.BoundVar;\r
  12 import org.simantics.scl.compiler.internal.codegen.references.Val;\r
  13 import org.simantics.scl.compiler.internal.codegen.references.ValRef;\r
  14 import org.simantics.scl.compiler.internal.codegen.ssa.binders.BoundVarBinder;\r
  15 import org.simantics.scl.compiler.internal.codegen.ssa.exits.Jump;\r
  16 import org.simantics.scl.compiler.internal.codegen.ssa.exits.Switch;\r
  17 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;\r
  18 import org.simantics.scl.compiler.internal.codegen.utils.CopyContext;\r
  19 import org.simantics.scl.compiler.internal.codegen.utils.MethodBuilder;\r
  20 import org.simantics.scl.compiler.internal.codegen.utils.Printable;\r
  21 import org.simantics.scl.compiler.internal.codegen.utils.PrintingContext;\r
  22 import org.simantics.scl.compiler.internal.codegen.utils.SSALambdaLiftingContext;\r
  23 import org.simantics.scl.compiler.internal.codegen.utils.SSASimplificationContext;\r
  24 import org.simantics.scl.compiler.internal.codegen.utils.SSAValidationContext;\r
  25 import org.simantics.scl.compiler.top.SCLCompilerConfiguration;\r
  26 import org.simantics.scl.compiler.types.TVar;\r
  27 import org.simantics.scl.compiler.types.Type;\r
  28 import org.simantics.scl.compiler.types.Types;\r
  29 \r
  30 public final class SSABlock extends Cont implements Printable, BoundVarBinder {\r
  31     public static final SSABlock[] EMPTY_ARRAY = new SSABlock[0];\r
  32     \r
  33     BoundVar[] parameters;\r
  34     \r
  35     SSAFunction parent;\r
  36     SSABlock prev;\r
  37     SSABlock next;\r
  38     SSAStatement firstStatement;\r
  39     SSAStatement lastStatement;\r
  40     SSAExit exit;\r
  41     \r
  42     public SSABlock(Type ... parameterTypes) {\r
  43         parameters = new BoundVar[parameterTypes.length];\r
  44         for(int i=0;i<parameterTypes.length;++i) {\r
  45             BoundVar parameter = new BoundVar(parameterTypes[i]); \r
  46             parameters[i] = parameter;\r
  47             parameter.parent = this;\r
  48         }\r
  49     }\r
  50     \r
  51     public SSABlock(BoundVar[] parameters) {    \r
  52         this.parameters = parameters;\r
  53         for(BoundVar parameter : parameters)\r
  54             parameter.parent = this;\r
  55     }\r
  56 \r
  57     public SSAFunction getParent() {\r
  58         return parent;\r
  59     }\r
  60     \r
  61     public SSABlock getNext() {\r
  62         return next;\r
  63     }\r
  64     \r
  65     public SSABlock getPrev() {\r
  66         return prev;\r
  67     }\r
  68     \r
  69     public SSAExit getExit() {\r
  70         return exit;\r
  71     }\r
  72     \r
  73     public void removeStatements() {\r
  74         this.firstStatement = null;\r
  75         this.lastStatement = null; \r
  76     }\r
  77     \r
  78     @Override\r
  79     public int getArity() {\r
  80         return parameters.length;\r
  81     }\r
  82     \r
  83     public int getStatementCount() {\r
  84         int count = 0;\r
  85         for(SSAStatement stat = firstStatement;stat != null;stat = stat.next)\r
  86             ++count;\r
  87         return count;\r
  88     }\r
  89     \r
  90     @Override\r
  91     public Type getParameterType(int parameterId) {\r
  92         return parameters[parameterId].getType();\r
  93     }\r
  94     \r
  95     public Type[] getParameterTypes() {\r
  96         return Types.getTypes(parameters);\r
  97     }\r
  98     \r
  99     public BoundVar[] getParameters() {\r
 100         return parameters;\r
 101     }\r
 102     \r
 103     public void setExit(SSAExit exit) {\r
 104         this.exit = exit;\r
 105         exit.parent = this;\r
 106     }\r
 107 \r
 108     public void detach() {\r
 109         if(prev == null)\r
 110             parent.firstBlock = next;\r
 111         else\r
 112             prev.next = next;\r
 113         if(next == null)\r
 114             parent.lastBlock = prev;\r
 115         else\r
 116             next.prev = prev;\r
 117         if(parent.firstBlock == null)\r
 118             throw new InternalCompilerError();\r
 119     }\r
 120 \r
 121     public void remove() {\r
 122         detach();\r
 123         destroy();\r
 124     }\r
 125     \r
 126     public void destroy() {\r
 127         for(SSAStatement statement = firstStatement; statement != null; statement = statement.next)\r
 128             statement.destroy();\r
 129         exit.destroy();\r
 130     }\r
 131 \r
 132     public void addStatement(SSAStatement stat) {\r
 133         if(SCLCompilerConfiguration.DEBUG) {\r
 134             if((firstStatement == null) != (lastStatement == null))\r
 135                 throw new InternalCompilerError();\r
 136         }\r
 137         stat.parent = this;\r
 138         if(lastStatement == null) {\r
 139             firstStatement = lastStatement = stat;\r
 140             stat.next = stat.prev = null;            \r
 141         }\r
 142         else {\r
 143             lastStatement.next = stat;\r
 144             stat.prev = lastStatement;\r
 145             stat.next = null;\r
 146             lastStatement = stat;\r
 147         }\r
 148     }\r
 149     \r
 150     public void generateCode(MethodBuilder mb) {\r
 151         mb.setLocation(this);\r
 152         for(SSAStatement stat = firstStatement; stat != null; stat = stat.next)\r
 153             stat.generateCode(mb);\r
 154         exit.generateCode(mb);\r
 155     }\r
 156 \r
 157     public void toString(PrintingContext context) {\r
 158         context.indentation();\r
 159         context.append(this);\r
 160         context.append("(" + occurrenceCount() + ")");\r
 161         parametersToString(context);\r
 162         context.append(" =\n");\r
 163         bodyToString(context);\r
 164     }\r
 165     \r
 166     public void parametersToString(PrintingContext context) {\r
 167         for(BoundVar parameter : parameters) {\r
 168             context.append(' ');\r
 169             if(parameter.hasNoOccurences()) {\r
 170                 context.append('(');\r
 171                 context.append('_');\r
 172                 context.append(" :: ");\r
 173                 context.append(parameter.getType());\r
 174                 context.append(')');\r
 175             }\r
 176             else {\r
 177                 context.append('(');\r
 178                 context.append(parameter);\r
 179                 context.append(" :: ");\r
 180                 context.append(parameter.getType());\r
 181                 context.append(')');\r
 182             }\r
 183         }\r
 184     }\r
 185     \r
 186     public void bodyToString(PrintingContext context) {\r
 187         context.indent();\r
 188         for(SSAStatement statement = firstStatement; statement != null; statement = statement.next)\r
 189             statement.toString(context);\r
 190         context.indentation();\r
 191         exit.toString(context);\r
 192         context.dedent();\r
 193     }\r
 194 \r
 195     public void validate(SSAValidationContext context) {\r
 196         if(exit.getParent() != this)\r
 197             throw new InternalCompilerError();\r
 198         for(BoundVar parameter : parameters) {         \r
 199             context.validate(parameter);\r
 200             if(parameter.parent != this)\r
 201                 throw new InternalCompilerError();\r
 202         }\r
 203         for(SSAStatement statement = firstStatement; statement != null; statement = statement.next) {\r
 204             if(statement.getParent() != this)\r
 205                 throw new InternalCompilerError();\r
 206             statement.validate(context);\r
 207         }\r
 208         exit.validate(context);\r
 209                 \r
 210         {\r
 211             SSAStatement last = firstStatement;\r
 212             if(last != null) {\r
 213                 while(last.next != null)\r
 214                     last = last.next;\r
 215             }\r
 216             if(last != lastStatement)\r
 217                 throw new InternalCompilerError();\r
 218         }\r
 219     }\r
 220 \r
 221     public void simplify(SSASimplificationContext context) {\r
 222         if(hasNoOccurences() && parent.firstBlock != this) {\r
 223             remove();\r
 224             context.markModified("dead-block");\r
 225             return;\r
 226         }\r
 227         \r
 228         tryToImproveParameters(context);\r
 229         \r
 230         // Simplify statements and exit\r
 231         for(SSAStatement statement = firstStatement; statement != null; statement = statement.next)\r
 232             statement.simplify(context);\r
 233         exit.simplify(context);\r
 234         \r
 235         // Simplifications to this block\r
 236         if(exit instanceof Switch) {\r
 237             if(simplifySwitch()) {\r
 238                 context.markModified("beta-switch");\r
 239             }\r
 240         }\r
 241         if(exit instanceof Jump) {\r
 242             if(firstStatement == null && parent.firstBlock != this) {\r
 243                 if(etaBlock(context)) {\r
 244                     context.markModified("eta-block");\r
 245                     return;\r
 246                 }\r
 247                 else if(inlineJump()) {\r
 248                     context.markModified("beta-block");\r
 249                     return;\r
 250                 }\r
 251             }\r
 252             else {\r
 253                 if(optimizeTailSelfCall()) {\r
 254                     context.markModified("simplify-tail-call");\r
 255                     return;\r
 256                 }\r
 257                 else if(inlineJump()) {\r
 258                     context.markModified("beta-block");\r
 259                     return;\r
 260                 }\r
 261             }\r
 262         }        \r
 263     }\r
 264 \r
 265     private void tryToImproveParameters(SSASimplificationContext context) {\r
 266         if(parent.firstBlock == this)\r
 267             return;\r
 268         if(parameters.length == 0)\r
 269             return;\r
 270         for(ContRef ref = getOccurrence(); ref != null; ref = ref.getNext())\r
 271             if(!(ref.getParent() instanceof Jump))\r
 272                 return;\r
 273         boolean modified = false;\r
 274         for(int i=0;i<parameters.length;++i)\r
 275             if(tryToImproveParameter(i)) {\r
 276                 --i;\r
 277                 modified = true;\r
 278             }\r
 279         if(modified)\r
 280             context.markModified("improve-parameters");\r
 281     }\r
 282 \r
 283     private boolean tryToImproveParameter(int position) {\r
 284         BoundVar parameter = parameters[position];\r
 285         Val constant = null;\r
 286         ValRef constantRef = null;\r
 287         for(ContRef ref = getOccurrence(); ref != null; ref = ref.getNext()) {\r
 288             Jump jump = (Jump)ref.getParent();\r
 289             ValRef valRef = jump.getParameters()[position];\r
 290             Val val = valRef.getBinding();\r
 291             if(val == parameter)\r
 292                 continue;\r
 293             if(constant == null) {\r
 294                 constant = val;\r
 295                 constantRef = valRef;\r
 296                 continue;\r
 297             }\r
 298             if(val != constant)\r
 299                 return false;\r
 300         }\r
 301         if(constant == null)\r
 302             return false; // This is a strange case, because we cannot get the parameter anywhere\r
 303         parameter.replaceBy(constantRef);\r
 304         \r
 305         for(ContRef ref = getOccurrence(); ref != null; ref = ref.getNext()) {\r
 306             Jump jump = (Jump)ref.getParent();\r
 307             jump.setParameters(removeAt(jump.getParameters(), position));\r
 308         }\r
 309         \r
 310         parameters = removeAt(parameters, position);\r
 311         return true;\r
 312     }\r
 313     \r
 314     private static BoundVar[] removeAt(BoundVar[] vars, int pos) {\r
 315         BoundVar[] result = new BoundVar[vars.length-1];\r
 316         for(int i=0;i<pos;++i)\r
 317             result[i] = vars[i];\r
 318         for(int i=pos+1;i<vars.length;++i)\r
 319             result[i-1] = vars[i];\r
 320         return result;\r
 321     }\r
 322 \r
 323     private static ValRef[] removeAt(ValRef[] vars, int pos) {\r
 324         ValRef[] result = new ValRef[vars.length-1];\r
 325         for(int i=0;i<pos;++i)\r
 326             result[i] = vars[i];\r
 327         vars[pos].remove();\r
 328         for(int i=pos+1;i<vars.length;++i)\r
 329             result[i-1] = vars[i];\r
 330         return result;\r
 331     }\r
 332     \r
 333     private boolean optimizeTailSelfCall() {\r
 334         Jump jump = (Jump)exit;\r
 335         if(jump.getTarget().getBinding() != parent.returnCont)\r
 336             return false;\r
 337         if(jump.getParameters().length != 1)\r
 338             return false;\r
 339         if(lastStatement == null || !(lastStatement instanceof LetApply))\r
 340             return false;\r
 341         LetApply apply = (LetApply)lastStatement;\r
 342         SSABlock initialBlock = parent.firstBlock;\r
 343         if(initialBlock.parameters.length != apply.getParameters().length)\r
 344             return false;\r
 345         Val function = apply.getFunction().getBinding();\r
 346         if(function != parent.target)\r
 347             return false;\r
 348         \r
 349         // Do modifications\r
 350         apply.detach();\r
 351         apply.getFunction().remove();\r
 352         jump.getTarget().remove();\r
 353         jump.setTarget(initialBlock.createOccurrence());\r
 354         jump.setParameters(apply.getParameters());\r
 355         \r
 356         return true;\r
 357     }\r
 358 \r
 359     private boolean etaBlock(SSASimplificationContext context) {\r
 360         Jump jump = (Jump)exit;\r
 361         if(parameters.length != jump.getParameters().length)\r
 362             return false;\r
 363         for(int i=0;i<parameters.length;++i)\r
 364             if(parameters[i] != jump.getParameters()[i].getBinding() ||\r
 365                parameters[i].hasMoreThanOneOccurences())\r
 366                 return false;\r
 367         \r
 368         replaceWith(jump.getTarget().getBinding());\r
 369         remove();\r
 370         return true;\r
 371     }\r
 372     \r
 373     private boolean simplifySwitch() {\r
 374         Switch sw = (Switch)exit;\r
 375         ValRef scrutineeRef = sw.getScrutinee();\r
 376         Val scrutinee = scrutineeRef.getBinding();\r
 377         if(scrutinee instanceof BoundVar) {\r
 378             BoundVarBinder parent = ((BoundVar)scrutinee).parent;\r
 379             if(!(parent instanceof LetApply))\r
 380                 return false;\r
 381             LetApply apply = (LetApply)parent;\r
 382             Val function = apply.getFunction().getBinding();\r
 383             if(!(function instanceof Constant) || function instanceof SCLConstant)\r
 384                 return false;\r
 385             for(BranchRef branch : sw.getBranches()) {\r
 386                 if(branch.constructor == function) {\r
 387                     sw.destroy();\r
 388                     setExit(new Jump(branch.cont.getBinding().createOccurrence(), \r
 389                             ValRef.copy(apply.getParameters())));\r
 390                     return true;\r
 391                 }\r
 392             }\r
 393         }\r
 394         else if(scrutinee instanceof Constant) {\r
 395             if(sw.getBranches().length == 1) {\r
 396                 BranchRef branch = sw.getBranches()[0];\r
 397                 if(branch.constructor == scrutinee) {\r
 398                     /**\r
 399                      * Optimizes for example\r
 400                      *      switch ()\r
 401                      *          () -> [a]\r
 402                      * ===>\r
 403                      *      [a]\r
 404                      */\r
 405                     sw.destroy();\r
 406                     setExit(new Jump(branch.cont.getBinding().createOccurrence()));\r
 407                 }\r
 408             }\r
 409         }\r
 410         return false;\r
 411     }\r
 412     \r
 413     private boolean inlineJump() {\r
 414         Jump jump = (Jump)exit;\r
 415         Cont target = jump.getTarget().getBinding();\r
 416         if(!(target instanceof SSABlock))\r
 417             return false;\r
 418         if(target.hasMoreThanOneOccurences())\r
 419             return false;\r
 420         SSABlock block = (SSABlock)target;\r
 421         if(block == parent.firstBlock || block == this)\r
 422             return false;\r
 423         \r
 424         /*System.out.println(">> BEFORE INLINE >>");\r
 425         System.out.println(getParent());\r
 426         System.out.println(">> THIS BLOCK >>");\r
 427         System.out.println(this);\r
 428         System.out.println(">> TARGET BLOCK >>");\r
 429         System.out.println(block);*/\r
 430                 \r
 431         mergeStatements(block);\r
 432 \r
 433         for(int i=0;i<jump.getParameters().length;++i)\r
 434             block.parameters[i].replaceBy(jump.getParameters()[i]);\r
 435         block.detach();\r
 436         \r
 437         jump.destroy();\r
 438         setExit(block.exit);       \r
 439         \r
 440         /*System.out.println(">> AFTER INLINE >>");\r
 441         System.out.println(getParent());\r
 442         System.out.println(">> THIS BLOCK >>");\r
 443         System.out.println(this);\r
 444         System.out.println(">>>>>>>>>>>>>>>>>>");*/\r
 445         return true;\r
 446     }\r
 447     \r
 448     private void mergeStatements(SSABlock block) {\r
 449         if(SCLCompilerConfiguration.DEBUG) {\r
 450             SSAStatement last = firstStatement;\r
 451             if(last != null) {\r
 452                 while(last.next != null)\r
 453                     last = last.next;\r
 454             }\r
 455             if(last != lastStatement)\r
 456                 throw new InternalCompilerError();\r
 457         }\r
 458         SSAStatement stat = block.firstStatement;\r
 459         while(stat != null) {\r
 460             SSAStatement next = stat.next;\r
 461             addStatement(stat);\r
 462             stat = next;\r
 463         }\r
 464     }\r
 465 \r
 466     @Override\r
 467     public String toString() {\r
 468         PrintingContext context = new PrintingContext();\r
 469         toString(context);\r
 470         return context.toString();\r
 471     }\r
 472 \r
 473     public void markGenerateOnFly() {\r
 474         for(SSAStatement stat = firstStatement; stat != null; stat = stat.next)\r
 475             stat.markGenerateOnFly();        \r
 476     }\r
 477     \r
 478     public SSABlock copy(CopyContext context) {\r
 479         SSABlock newBlock = new SSABlock(context.copy(parameters));\r
 480         context.put(this, newBlock);\r
 481         for(SSAStatement statement = firstStatement;\r
 482                 statement != null; statement = statement.next)\r
 483             newBlock.addStatement(statement.copy(context));\r
 484         newBlock.setExit(exit.copy(context)); \r
 485         return newBlock;\r
 486     }\r
 487 \r
 488     public void setParameters(BoundVar[] parameters) {\r
 489         for(BoundVar parameter : parameters)\r
 490             parameter.parent = this;\r
 491         this.parameters = parameters;\r
 492     }\r
 493 \r
 494     @Override\r
 495     public void replace(TVar[] vars, Type[] replacements) {\r
 496         for(BoundVar parameter : parameters)\r
 497             parameter.replace(vars, replacements);\r
 498         for(SSAStatement statement = firstStatement;\r
 499                 statement != null; statement = statement.next)\r
 500             statement.replace(vars, replacements);\r
 501         exit.replace(vars, replacements);\r
 502     }\r
 503 \r
 504     public void collectFreeVariables(SSAFunction function, ArrayList<ValRef> vars) {\r
 505         for(SSAStatement statement = firstStatement;\r
 506                 statement != null; statement = statement.next)\r
 507             statement.collectFreeVariables(function, vars);\r
 508         exit.collectFreeVariables(function, vars);\r
 509     }\r
 510 \r
 511     @Override\r
 512     public SSAFunction getParentFunction() {\r
 513         return parent;\r
 514     }\r
 515 \r
 516     public void lambdaLift(SSALambdaLiftingContext context) {\r
 517         for(SSAStatement statement = firstStatement;\r
 518                 statement != null; statement = statement.next)\r
 519             statement.lambdaLift(context);\r
 520     }\r
 521     \r
 522     public SSAStatement getFirstStatement() {\r
 523         return firstStatement;\r
 524     }\r
 525 \r
 526     public void setParameter(int position, BoundVar target) {\r
 527         parameters[position] = target;\r
 528         target.parent = this;\r
 529     }\r
 530 \r
 531     public void prepare(MethodBuilder mb) {\r
 532         for(SSAStatement stat = firstStatement; stat != null; stat = stat.next)\r
 533             stat.prepare(mb);\r
 534         exit.prepare(mb);\r
 535     }\r
 536     \r
 537 }\r