1 package org.simantics.scl.compiler.internal.codegen.ssa;
\r
3 import java.util.ArrayList;
\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
30 public final class SSABlock extends Cont implements Printable, BoundVarBinder {
\r
31 public static final SSABlock[] EMPTY_ARRAY = new SSABlock[0];
\r
33 BoundVar[] parameters;
\r
38 SSAStatement firstStatement;
\r
39 SSAStatement lastStatement;
\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
51 public SSABlock(BoundVar[] parameters) {
\r
52 this.parameters = parameters;
\r
53 for(BoundVar parameter : parameters)
\r
54 parameter.parent = this;
\r
57 public SSAFunction getParent() {
\r
61 public SSABlock getNext() {
\r
65 public SSABlock getPrev() {
\r
69 public SSAExit getExit() {
\r
73 public void removeStatements() {
\r
74 this.firstStatement = null;
\r
75 this.lastStatement = null;
\r
79 public int getArity() {
\r
80 return parameters.length;
\r
83 public int getStatementCount() {
\r
85 for(SSAStatement stat = firstStatement;stat != null;stat = stat.next)
\r
91 public Type getParameterType(int parameterId) {
\r
92 return parameters[parameterId].getType();
\r
95 public Type[] getParameterTypes() {
\r
96 return Types.getTypes(parameters);
\r
99 public BoundVar[] getParameters() {
\r
103 public void setExit(SSAExit exit) {
\r
105 exit.parent = this;
\r
108 public void detach() {
\r
110 parent.firstBlock = next;
\r
114 parent.lastBlock = prev;
\r
117 if(parent.firstBlock == null)
\r
118 throw new InternalCompilerError();
\r
121 public void remove() {
\r
126 public void destroy() {
\r
127 for(SSAStatement statement = firstStatement; statement != null; statement = statement.next)
\r
128 statement.destroy();
\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
137 stat.parent = this;
\r
138 if(lastStatement == null) {
\r
139 firstStatement = lastStatement = stat;
\r
140 stat.next = stat.prev = null;
\r
143 lastStatement.next = stat;
\r
144 stat.prev = lastStatement;
\r
146 lastStatement = stat;
\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
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
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
177 context.append('(');
\r
178 context.append(parameter);
\r
179 context.append(" :: ");
\r
180 context.append(parameter.getType());
\r
181 context.append(')');
\r
186 public void bodyToString(PrintingContext context) {
\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
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
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
208 exit.validate(context);
\r
211 SSAStatement last = firstStatement;
\r
213 while(last.next != null)
\r
216 if(last != lastStatement)
\r
217 throw new InternalCompilerError();
\r
221 public void simplify(SSASimplificationContext context) {
\r
222 if(hasNoOccurences() && parent.firstBlock != this) {
\r
224 context.markModified("dead-block");
\r
228 tryToImproveParameters(context);
\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
235 // Simplifications to this block
\r
236 if(exit instanceof Switch) {
\r
237 if(simplifySwitch()) {
\r
238 context.markModified("beta-switch");
\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
247 else if(inlineJump()) {
\r
248 context.markModified("beta-block");
\r
253 if(optimizeTailSelfCall()) {
\r
254 context.markModified("simplify-tail-call");
\r
257 else if(inlineJump()) {
\r
258 context.markModified("beta-block");
\r
265 private void tryToImproveParameters(SSASimplificationContext context) {
\r
266 if(parent.firstBlock == this)
\r
268 if(parameters.length == 0)
\r
270 for(ContRef ref = getOccurrence(); ref != null; ref = ref.getNext())
\r
271 if(!(ref.getParent() instanceof Jump))
\r
273 boolean modified = false;
\r
274 for(int i=0;i<parameters.length;++i)
\r
275 if(tryToImproveParameter(i)) {
\r
280 context.markModified("improve-parameters");
\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
293 if(constant == null) {
\r
295 constantRef = valRef;
\r
298 if(val != constant)
\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
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
310 parameters = removeAt(parameters, position);
\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
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
333 private boolean optimizeTailSelfCall() {
\r
334 Jump jump = (Jump)exit;
\r
335 if(jump.getTarget().getBinding() != parent.returnCont)
\r
337 if(jump.getParameters().length != 1)
\r
339 if(lastStatement == null || !(lastStatement instanceof LetApply))
\r
341 LetApply apply = (LetApply)lastStatement;
\r
342 SSABlock initialBlock = parent.firstBlock;
\r
343 if(initialBlock.parameters.length != apply.getParameters().length)
\r
345 Val function = apply.getFunction().getBinding();
\r
346 if(function != parent.target)
\r
349 // Do modifications
\r
351 apply.getFunction().remove();
\r
352 jump.getTarget().remove();
\r
353 jump.setTarget(initialBlock.createOccurrence());
\r
354 jump.setParameters(apply.getParameters());
\r
359 private boolean etaBlock(SSASimplificationContext context) {
\r
360 Jump jump = (Jump)exit;
\r
361 if(parameters.length != jump.getParameters().length)
\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
368 replaceWith(jump.getTarget().getBinding());
\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
381 LetApply apply = (LetApply)parent;
\r
382 Val function = apply.getFunction().getBinding();
\r
383 if(!(function instanceof Constant) || function instanceof SCLConstant)
\r
385 for(BranchRef branch : sw.getBranches()) {
\r
386 if(branch.constructor == function) {
\r
388 setExit(new Jump(branch.cont.getBinding().createOccurrence(),
\r
389 ValRef.copy(apply.getParameters())));
\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
399 * Optimizes for example
\r
406 setExit(new Jump(branch.cont.getBinding().createOccurrence()));
\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
418 if(target.hasMoreThanOneOccurences())
\r
420 SSABlock block = (SSABlock)target;
\r
421 if(block == parent.firstBlock || block == this)
\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
431 mergeStatements(block);
\r
433 for(int i=0;i<jump.getParameters().length;++i)
\r
434 block.parameters[i].replaceBy(jump.getParameters()[i]);
\r
438 setExit(block.exit);
\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
448 private void mergeStatements(SSABlock block) {
\r
449 if(SCLCompilerConfiguration.DEBUG) {
\r
450 SSAStatement last = firstStatement;
\r
452 while(last.next != null)
\r
455 if(last != lastStatement)
\r
456 throw new InternalCompilerError();
\r
458 SSAStatement stat = block.firstStatement;
\r
459 while(stat != null) {
\r
460 SSAStatement next = stat.next;
\r
461 addStatement(stat);
\r
467 public String toString() {
\r
468 PrintingContext context = new PrintingContext();
\r
470 return context.toString();
\r
473 public void markGenerateOnFly() {
\r
474 for(SSAStatement stat = firstStatement; stat != null; stat = stat.next)
\r
475 stat.markGenerateOnFly();
\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
488 public void setParameters(BoundVar[] parameters) {
\r
489 for(BoundVar parameter : parameters)
\r
490 parameter.parent = this;
\r
491 this.parameters = parameters;
\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
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
512 public SSAFunction getParentFunction() {
\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
522 public SSAStatement getFirstStatement() {
\r
523 return firstStatement;
\r
526 public void setParameter(int position, BoundVar target) {
\r
527 parameters[position] = target;
\r
528 target.parent = this;
\r
531 public void prepare(MethodBuilder mb) {
\r
532 for(SSAStatement stat = firstStatement; stat != null; stat = stat.next)
\r