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

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