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