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.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
31 public final class SSABlock extends Cont implements Printable, BoundVarBinder {
\r
32 public static final SSABlock[] EMPTY_ARRAY = new SSABlock[0];
\r
34 BoundVar[] parameters;
\r
39 SSAStatement firstStatement;
\r
40 SSAStatement lastStatement;
\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
52 public SSABlock(BoundVar[] parameters) {
\r
53 this.parameters = parameters;
\r
54 for(BoundVar parameter : parameters)
\r
55 parameter.parent = this;
\r
58 public SSAFunction getParent() {
\r
62 public SSABlock getNext() {
\r
66 public SSABlock getPrev() {
\r
70 public SSAExit getExit() {
\r
74 public void removeStatements() {
\r
75 this.firstStatement = null;
\r
76 this.lastStatement = null;
\r
80 public int getArity() {
\r
81 return parameters.length;
\r
84 public int getStatementCount() {
\r
86 for(SSAStatement stat = firstStatement;stat != null;stat = stat.next)
\r
92 public Type getParameterType(int parameterId) {
\r
93 return parameters[parameterId].getType();
\r
96 public Type[] getParameterTypes() {
\r
97 return Types.getTypes(parameters);
\r
100 public BoundVar[] getParameters() {
\r
104 public void setExit(SSAExit exit) {
\r
106 exit.parent = this;
\r
109 public void detach() {
\r
111 parent.firstBlock = next;
\r
115 parent.lastBlock = prev;
\r
118 if(parent.firstBlock == null)
\r
119 throw new InternalCompilerError();
\r
122 public void remove() {
\r
127 public void destroy() {
\r
128 for(SSAStatement statement = firstStatement; statement != null; statement = statement.next)
\r
129 statement.destroy();
\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
138 stat.parent = this;
\r
139 if(lastStatement == null) {
\r
140 firstStatement = lastStatement = stat;
\r
141 stat.next = stat.prev = null;
\r
144 lastStatement.next = stat;
\r
145 stat.prev = lastStatement;
\r
147 lastStatement = stat;
\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
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
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
178 context.append('(');
\r
179 context.append(parameter);
\r
180 context.append(" :: ");
\r
181 context.append(parameter.getType());
\r
182 context.append(')');
\r
187 public void bodyToString(PrintingContext context) {
\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
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
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
209 exit.validate(context);
\r
212 SSAStatement last = firstStatement;
\r
214 while(last.next != null)
\r
217 if(last != lastStatement)
\r
218 throw new InternalCompilerError();
\r
222 public void simplify(SSASimplificationContext context) {
\r
223 if(hasNoOccurences() && parent.firstBlock != this) {
\r
225 context.markModified("dead-block");
\r
229 tryToImproveParameters(context);
\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
236 // Simplifications to this block
\r
237 if(exit instanceof Switch) {
\r
238 if(simplifySwitch()) {
\r
239 context.markModified("beta-switch");
\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
248 else if(inlineJump()) {
\r
249 context.markModified("beta-block");
\r
254 if(optimizeTailSelfCall()) {
\r
255 context.markModified("simplify-tail-call");
\r
258 else if(inlineJump()) {
\r
259 context.markModified("beta-block");
\r
266 private void tryToImproveParameters(SSASimplificationContext context) {
\r
267 if(parent.firstBlock == this)
\r
269 if(parameters.length == 0)
\r
271 for(ContRef ref = getOccurrence(); ref != null; ref = ref.getNext())
\r
272 if(!(ref.getParent() instanceof Jump))
\r
274 boolean modified = false;
\r
275 for(int i=0;i<parameters.length;++i)
\r
276 if(tryToImproveParameter(i)) {
\r
281 context.markModified("improve-parameters");
\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
294 if(constant == null) {
\r
296 constantRef = valRef;
\r
299 if(val != constant)
\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
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
311 parameters = removeAt(parameters, position);
\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
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
334 private boolean optimizeTailSelfCall() {
\r
335 Jump jump = (Jump)exit;
\r
336 if(jump.getTarget().getBinding() != parent.returnCont)
\r
338 if(jump.getParameters().length != 1)
\r
340 if(lastStatement == null || !(lastStatement instanceof LetApply))
\r
342 LetApply apply = (LetApply)lastStatement;
\r
343 SSABlock initialBlock = parent.firstBlock;
\r
344 if(initialBlock.parameters.length != apply.getParameters().length)
\r
346 Val function = apply.getFunction().getBinding();
\r
347 if(function != parent.target)
\r
350 // Do modifications
\r
352 apply.getFunction().remove();
\r
353 jump.getTarget().remove();
\r
354 jump.setTarget(initialBlock.createOccurrence());
\r
355 jump.setParameters(apply.getParameters());
\r
360 private boolean etaBlock(SSASimplificationContext context) {
\r
361 Jump jump = (Jump)exit;
\r
362 if(parameters.length != jump.getParameters().length)
\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
369 replaceWith(jump.getTarget().getBinding());
\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
382 LetApply apply = (LetApply)parent;
\r
383 Val function = apply.getFunction().getBinding();
\r
384 if(!(function instanceof Constant) || function instanceof SCLConstant)
\r
386 for(BranchRef branch : sw.getBranches()) {
\r
387 if(branch.constructor == function) {
\r
389 setExit(new Jump(branch.cont.getBinding().createOccurrence(),
\r
390 ValRef.copy(apply.getParameters())));
\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
400 * Optimizes for example
\r
407 setExit(new Jump(branch.cont.getBinding().createOccurrence()));
\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
419 if(target.hasMoreThanOneOccurences())
\r
421 SSABlock block = (SSABlock)target;
\r
422 if(block == parent.firstBlock || block == this)
\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
432 mergeStatements(block);
\r
434 for(int i=0;i<jump.getParameters().length;++i)
\r
435 block.parameters[i].replaceBy(jump.getParameters()[i]);
\r
439 setExit(block.exit);
\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
449 private void mergeStatements(SSABlock block) {
\r
450 if(SCLCompilerConfiguration.DEBUG) {
\r
451 SSAStatement last = firstStatement;
\r
453 while(last.next != null)
\r
456 if(last != lastStatement)
\r
457 throw new InternalCompilerError();
\r
459 SSAStatement stat = block.firstStatement;
\r
460 while(stat != null) {
\r
461 SSAStatement next = stat.next;
\r
462 addStatement(stat);
\r
468 public String toString() {
\r
469 PrintingContext context = new PrintingContext();
\r
471 return context.toString();
\r
474 public void markGenerateOnFly() {
\r
475 for(SSAStatement stat = firstStatement; stat != null; stat = stat.next)
\r
476 stat.markGenerateOnFly();
\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
489 public void setParameters(BoundVar[] parameters) {
\r
490 for(BoundVar parameter : parameters)
\r
491 parameter.parent = this;
\r
492 this.parameters = parameters;
\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
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
513 public SSAFunction getParentFunction() {
\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
523 public SSAStatement getFirstStatement() {
\r
524 return firstStatement;
\r
527 public void setParameter(int position, BoundVar target) {
\r
528 parameters[position] = target;
\r
529 target.parent = this;
\r
532 public void prepare(MethodBuilder mb) {
\r
533 for(SSAStatement stat = firstStatement; stat != null; stat = stat.next)
\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