1 package org.simantics.scl.compiler.internal.codegen.ssa;
3 import java.util.ArrayList;
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;
31 public final class SSABlock extends Cont implements Printable, BoundVarBinder {
32 public static final SSABlock[] EMPTY_ARRAY = new SSABlock[0];
34 BoundVar[] parameters;
39 SSAStatement firstStatement;
40 SSAStatement lastStatement;
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;
52 public SSABlock(BoundVar[] parameters) {
53 this.parameters = parameters;
54 for(BoundVar parameter : parameters)
55 parameter.parent = this;
58 public SSAFunction getParent() {
62 public SSABlock getNext() {
66 public SSABlock getPrev() {
70 public SSAExit getExit() {
74 public void removeStatements() {
75 this.firstStatement = null;
76 this.lastStatement = null;
80 public int getArity() {
81 return parameters.length;
84 public int getStatementCount() {
86 for(SSAStatement stat = firstStatement;stat != null;stat = stat.next)
92 public Type getParameterType(int parameterId) {
93 return parameters[parameterId].getType();
96 public Type[] getParameterTypes() {
97 return Types.getTypes(parameters);
100 public BoundVar[] getParameters() {
104 public void setExit(SSAExit exit) {
109 public void detach() {
111 parent.firstBlock = next;
115 parent.lastBlock = prev;
118 if(parent.firstBlock == null)
119 throw new InternalCompilerError();
122 public void remove() {
127 public void destroy() {
128 for(SSAStatement statement = firstStatement; statement != null; statement = statement.next)
133 public void addStatement(SSAStatement stat) {
134 if(SCLCompilerConfiguration.DEBUG) {
135 if((firstStatement == null) != (lastStatement == null))
136 throw new InternalCompilerError();
139 if(lastStatement == null) {
140 firstStatement = lastStatement = stat;
141 stat.next = stat.prev = null;
144 lastStatement.next = stat;
145 stat.prev = lastStatement;
147 lastStatement = stat;
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);
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);
167 public void parametersToString(PrintingContext context) {
168 for(BoundVar parameter : parameters) {
170 if(parameter.hasNoOccurences()) {
173 context.append(" :: ");
174 context.append(parameter.getType());
179 context.append(parameter);
180 context.append(" :: ");
181 context.append(parameter.getType());
187 public void bodyToString(PrintingContext context) {
189 for(SSAStatement statement = firstStatement; statement != null; statement = statement.next)
190 statement.toString(context);
191 context.indentation();
192 exit.toString(context);
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();
204 for(SSAStatement statement = firstStatement; statement != null; statement = statement.next) {
205 if(statement.getParent() != this)
206 throw new InternalCompilerError();
207 statement.validate(context);
209 exit.validate(context);
212 SSAStatement last = firstStatement;
214 while(last.next != null)
217 if(last != lastStatement)
218 throw new InternalCompilerError();
222 public void simplify(SSASimplificationContext context) {
223 if(hasNoOccurences() && parent.firstBlock != this) {
225 context.markModified("dead-block");
229 tryToImproveParameters(context);
231 // Simplify statements and exit
232 for(SSAStatement statement = firstStatement; statement != null; statement = statement.next)
233 statement.simplify(context);
234 exit.simplify(context);
236 // Simplifications to this block
237 if(exit instanceof Switch) {
238 if(simplifySwitch()) {
239 context.markModified("beta-switch");
242 if(exit instanceof Jump) {
243 if(firstStatement == null && parent.firstBlock != this) {
244 if(etaBlock(context)) {
245 context.markModified("eta-block");
248 else if(inlineJump()) {
249 context.markModified("beta-block");
254 if(optimizeTailSelfCall()) {
255 context.markModified("simplify-tail-call");
258 else if(inlineJump()) {
259 context.markModified("beta-block");
266 private void tryToImproveParameters(SSASimplificationContext context) {
267 if(parent.firstBlock == this)
269 if(parameters.length == 0)
271 for(ContRef ref = getOccurrence(); ref != null; ref = ref.getNext())
272 if(!(ref.getParent() instanceof Jump))
274 boolean modified = false;
275 for(int i=0;i<parameters.length;++i)
276 if(tryToImproveParameter(i)) {
281 context.markModified("improve-parameters");
284 private boolean tryToImproveParameter(int position) {
285 BoundVar parameter = parameters[position];
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();
294 if(constant == null) {
296 constantRef = valRef;
303 return false; // This is a strange case, because we cannot get the parameter anywhere
304 parameter.replaceBy(constantRef);
306 for(ContRef ref = getOccurrence(); ref != null; ref = ref.getNext()) {
307 Jump jump = (Jump)ref.getParent();
308 jump.setParameters(removeAt(jump.getParameters(), position));
311 parameters = removeAt(parameters, position);
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)
319 for(int i=pos+1;i<vars.length;++i)
320 result[i-1] = vars[i];
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)
329 for(int i=pos+1;i<vars.length;++i)
330 result[i-1] = vars[i];
334 private boolean optimizeTailSelfCall() {
335 Jump jump = (Jump)exit;
336 if(jump.getTarget().getBinding() != parent.returnCont)
338 if(jump.getParameters().length != 1)
340 if(lastStatement == null || !(lastStatement instanceof LetApply))
342 LetApply apply = (LetApply)lastStatement;
343 SSABlock initialBlock = parent.firstBlock;
344 if(initialBlock.parameters.length != apply.getParameters().length)
346 Val function = apply.getFunction().getBinding();
347 if(function != parent.target)
352 apply.getFunction().remove();
353 jump.getTarget().remove();
354 jump.setTarget(initialBlock.createOccurrence());
355 jump.setParameters(apply.getParameters());
360 private boolean etaBlock(SSASimplificationContext context) {
361 Jump jump = (Jump)exit;
362 if(parameters.length != jump.getParameters().length)
364 for(int i=0;i<parameters.length;++i)
365 if(parameters[i] != jump.getParameters()[i].getBinding() ||
366 parameters[i].hasMoreThanOneOccurences())
369 replaceWith(jump.getTarget().getBinding());
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))
382 LetApply apply = (LetApply)parent;
383 Val function = apply.getFunction().getBinding();
384 if(!(function instanceof Constant) || function instanceof SCLConstant)
386 for(BranchRef branch : sw.getBranches()) {
387 if(branch.constructor == function) {
389 setExit(new Jump(branch.cont.getBinding().createOccurrence(),
390 ValRef.copy(apply.getParameters())));
395 else if(scrutinee instanceof Constant) {
396 if(sw.getBranches().length == 1) {
397 BranchRef branch = sw.getBranches()[0];
398 if(branch.constructor == scrutinee) {
400 * Optimizes for example
407 setExit(new Jump(branch.cont.getBinding().createOccurrence()));
414 private boolean inlineJump() {
415 Jump jump = (Jump)exit;
416 Cont target = jump.getTarget().getBinding();
417 if(!(target instanceof SSABlock))
419 if(target.hasMoreThanOneOccurences())
421 SSABlock block = (SSABlock)target;
422 if(block == parent.firstBlock || block == this)
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);*/
432 mergeStatements(block);
434 for(int i=0;i<jump.getParameters().length;++i)
435 block.parameters[i].replaceBy(jump.getParameters()[i]);
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(">>>>>>>>>>>>>>>>>>");*/
449 private void mergeStatements(SSABlock block) {
450 if(SCLCompilerConfiguration.DEBUG) {
451 SSAStatement last = firstStatement;
453 while(last.next != null)
456 if(last != lastStatement)
457 throw new InternalCompilerError();
459 SSAStatement stat = block.firstStatement;
460 while(stat != null) {
461 SSAStatement next = stat.next;
468 public String toString() {
469 PrintingContext context = new PrintingContext();
471 return context.toString();
474 public void markGenerateOnFly() {
475 for(SSAStatement stat = firstStatement; stat != null; stat = stat.next)
476 stat.markGenerateOnFly();
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));
489 public void setParameters(BoundVar[] parameters) {
490 for(BoundVar parameter : parameters)
491 parameter.parent = this;
492 this.parameters = parameters;
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);
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);
513 public SSAFunction getParentFunction() {
517 public void lambdaLift(SSALambdaLiftingContext context) {
518 for(SSAStatement statement = firstStatement;
519 statement != null; statement = statement.next)
520 statement.lambdaLift(context);
523 public SSAStatement getFirstStatement() {
524 return firstStatement;
527 public void setParameter(int position, BoundVar target) {
528 parameters[position] = target;
529 target.parent = this;
532 public void prepare(MethodBuilder mb) {
533 for(SSAStatement stat = firstStatement; stat != null; stat = stat.next)
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);