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