source: branches/dev-jk-2597/Compiler/ModelicaMiddleEnd/src/jastadd/scalarization/ScalarizeFunctions.jrag @ 13822

Last change on this file since 13822 was 13822, checked in by Jonathan Kämpe, 6 weeks ago

#5862 Now printing empty array subscripts in order to detect them in tests. Fixed a couple of occurences.

File size: 45.6 KB
Line 
1/*
2    Copyright (C) 2016 Modelon AB
3
4    This program is free software: you can redistribute it and/or modify
5    it under the terms of the GNU General Public License as published by
6    the Free Software Foundation, version 3 of the License.
7
8    This program is distributed in the hope that it will be useful,
9    but WITHOUT ANY WARRANTY; without even the implied warranty of
10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11    GNU General Public License for more details.
12
13    You should have received a copy of the GNU General Public License
14    along with this program.  If not, see <http://www.gnu.org/licenses/>.
15*/
16
17aspect FunctionScalarization {
18   
19    /**
20     * Scalarize the function, replacing all array assignments with separate scalar
21     *        assignments and scalarize all expressions.
22     */
23    public void FFunctionDecl.scalarize(boolean unroll) {
24        List<FStatement> stmts = new List<FStatement>();
25        List<FAttribute> attrs = new List<FAttribute>();
26        try {
27            FStatement.scalarizeStmtList(Scalarizer.function(getFFunctionVariables(), stmts, unroll), getFAlgorithm().getFStatements());
28        } catch (ModelicaException e) {
29            throw e;
30        } catch (Exception e) {
31            throw new org.jmodelica.util.exceptions.InternalCompilerError("Exception caught while scalarizing function'" + name() + "'", e);
32        }
33        setFAlgorithm(new FAlgorithm(stmts));
34        clearScalarized();  // Functions need scalarized = false in FAccesss
35        flushAllRecursive();
36    }
37   
38    /**
39     * Post processing FFunctionDecls after scalarization.
40     * Clear the scalarized flag for all FAccesss.
41     * Rewrite FTempAccessExp to FAccessExp
42     */
43    public void ASTNode.clearScalarized() {
44        for (ASTNode node : this)
45            node.clearScalarized();
46    }
47   
48    public void FAccess.clearScalarized() {
49        scalarized = false;
50    }
51   
52    private boolean FTempAccessExp.clearScalarized = false;
53    public void FTempAccessExp.clearScalarized() {
54        super.clearScalarized();
55        clearScalarized = true;
56    }
57   
58    rewrite FTempAccessExp {
59        when (clearScalarized) to FAccessExp new FAccessExp(getFAccess());
60    }
61   
62    /**
63     * Should this expression be extracted into its own statement?
64     */
65    syn boolean FExp.extractTemp(Scalarizer s);
66    eq FExp               .extractTemp(Scalarizer s) =
67            (!s.unroll() && extractTempArray() && extractTempContext()) || extractForIndexTemp();
68   
69    eq FAccessExp         .extractTemp(Scalarizer s) = super.extractTemp(s) && isSlice() && !isFunctionCallLeft();
70    eq FFunctionCall      .extractTemp(Scalarizer s) = isFunctionCallClause() || 
71            ((isFVectorFunctionCallArg() || !isFunctionCallIO()) &&
72                (isComposite() || isForIndexExp()));
73       
74    eq FSpatialDistExp    .extractTemp(Scalarizer s) = isFunctionCallClause() || super.extractTemp(s);
75    eq FVectorFunctionCall.extractTemp(Scalarizer s) = true;
76   
77   
78    syn boolean FExp .extractTempArray();
79    eq FExp          .extractTempArray() = isArray();
80    eq FMulExp       .extractTempArray() = getLeft().isArray() || getRight().isArray();
81    eq FReductionExp .extractTempArray() = getFExp().isArray();
82    eq FMinMaxExp    .extractTempArray() = getX().isArray();
83    eq FTempAccessExp.extractTempArray() = false;
84    eq FIfExp        .extractTempArray() = false;
85   
86    syn boolean FExp    .extractTempContext();
87    eq FExp             .extractTempContext() = isFunctionCallIO();
88    eq FMulExp          .extractTempContext() = isFunctionCallIO() || !isElementWise();
89    eq FArray           .extractTempContext() = !keepSimple();
90    eq FReductionExp    .extractTempContext() = true;
91    eq FMinMaxExp       .extractTempContext() = true;
92    eq FSizeExp         .extractTempContext() = true;
93    eq FAbstractCat     .extractTempContext() = true;
94    eq FAbstractDiagonal.extractTempContext() = true;
95    eq FVectorExp       .extractTempContext() = true;
96    eq FMatrixExp       .extractTempContext() = true;
97    eq FCross           .extractTempContext() = true;
98    eq FSkew            .extractTempContext() = true;
99    eq FSymmetric       .extractTempContext() = true;
100    eq FOuterProduct    .extractTempContext() = true;
101   
102    syn boolean FExp.extractForIndexTemp() = isForIndexExp();
103    eq FRangeExp.extractForIndexTemp()     = false;
104   
105    syn boolean FArray.keepSimple() = isFunctionCallIO() && !isFVectorFunctionCallArg()
106                && ndims() == 1 && !isIterArray() && type().isPrimitive();
107   
108   
109    inh boolean FExp.isFunctionCallIO();
110    eq BaseNode.getChild().isFunctionCallIO()         = false;
111    eq FFunctionCall.getArg().isFunctionCallIO()      = true;
112    eq FFunctionCallLeft.getFExp().isFunctionCallIO() = true;
113    eq FIfExp.getChild().isFunctionCallIO()           = isFunctionCallIO();
114   
115    inh boolean FExp.isForIndexExp();
116    eq BaseNode.getChild().isForIndexExp() = false;
117    eq FForIndex.getFExp().isForIndexExp() = true;
118   
119    inh boolean FExp.isFVectorFunctionCallArg();
120    eq BaseNode.getChild().isFVectorFunctionCallArg()          = false;
121    eq FVectorFunctionCall.getArg().isFVectorFunctionCallArg() = true;
122   
123    syn boolean FAssignStmt.extractTemp(Scalarizer.Algorithm s) {
124        if (type().isArray()) {
125            Set<FAbstractVariable> left = getLeft().usesInScalarizedExp(s);
126            Set<FAbstractVariable> right = getRight().usesInScalarizedExp(s);
127            for (FAbstractVariable fv : left) {
128                if (right.contains(fv)) {
129                    return true;
130                }
131            }
132        }
133        return false;
134    }
135   
136    syn Set<FAbstractVariable> FExp.usesInScalarizedExp(Scalarizer.Algorithm s) {
137        Set<FAbstractVariable> res = new HashSet<FAbstractVariable>();
138        usesInScalarizedExp(s, res);
139        return res;
140    }
141   
142    public void ASTNode.usesInScalarizedExp(Scalarizer.Algorithm s, Set<FAbstractVariable> res) {
143        for (ASTNode n : this)
144            n.usesInScalarizedExp(s, res);
145    }
146   
147    public void FExp.usesInScalarizedExp(Scalarizer.Algorithm s, Set<FAbstractVariable> res) {
148        if (!extractTemp(s)) {
149            super.usesInScalarizedExp(s, res);
150        }
151    }
152   
153    public void FAccessExp.usesInScalarizedExp(Scalarizer.Algorithm s, Set<FAbstractVariable> res) {
154        res.add(myFV());
155    }
156   
157    public void FSizeExp.usesInScalarizedExp(Scalarizer.Algorithm s, Set<FAbstractVariable> res) {
158       
159    }
160   
161    /**
162     * Traverser for {@link FExp#createArrayTemporaries(Scalarizer s)}.
163     */
164    public void ASTNode.createArrayTemporaries(Scalarizer s) {
165        for (ASTNode n : this)
166            n.createArrayTemporaries(s);
167    }
168   
169    public void Array.createArrayTemporaries(Scalarizer s);
170   
171    public void ArrayExp.createArrayTemporaries(Scalarizer s) {
172        super.createArrayTemporaries(s);
173    }
174   
175    /**
176     * Finds, extracts, and replaces expressions with temporaries
177     */
178    public void FExp.createArrayTemporaries(Scalarizer s) {
179        if (extractTemp(s)) {
180            if (!s.unroll()) {
181                unknownFunctionArrayTemporaries(s);
182                useTempVar = true;
183            } else {
184                knownArrayTemporaries(s);
185            }
186        } else {
187            createArrayTemporariesInChildren(s);
188        }
189    }
190   
191    public void FExp.createArrayTemporariesInChildren(Scalarizer s) {
192        for (ASTNode n : this) {
193            n.createArrayTemporaries(s);
194        }
195    }
196   
197    public void FIfExp.createArrayTemporariesInChildren(Scalarizer s) {
198        if (inFAlgorithm()) {
199            List thenClauses = new List();
200            List elseClauses = new List();
201            getIfExp().createArrayTemporaries(s);
202            getThenExp().createArrayTemporaries(s.block(thenClauses));
203            getElseExp().createArrayTemporaries(s.block(elseClauses));
204            if (thenClauses.getNumChild() > 0 || elseClauses.getNumChild() > 0) {
205                List<FIfWhenClause> cl = new List<FIfWhenClause>();
206                cl.add(new FIfClause(getIfExp().scalarize(s), thenClauses));
207                ((Scalarizer.Algorithm)s).add(new FIfStmtTemp(cl, elseClauses));
208            }
209        } else {
210            createArrayTemporariesIfBranch(null, s);
211        }
212    }
213   
214    public void FExp.createArrayTemporariesIfBranch(FExp ifExp, Scalarizer s) {
215        List thenClauses = new List();
216        List elseClauses = new List();
217        List<FAbstractVariable> thenVars = new List<FAbstractVariable>();
218        createArrayTemporaries(s.block(thenVars, thenClauses));
219        if (thenClauses.getNumChild() > 0) {
220            if (inFAlgorithm()) {
221                List<FIfWhenClause> cl = new List<FIfWhenClause>();
222                cl.add(new FIfClause(ifExp, thenClauses));
223                s.add(new FIfStmtTemp(cl, elseClauses));
224            } else {
225                for (FAbstractVariable fv : thenVars) {
226                    elseClauses.add(new FEquation(fv.createAccessExp(), fv.type().zeroLiteral()));
227                }
228                FElseEquation elseClause = new FElseEquation(EquationType.NORMAL, elseClauses);
229                FIfEquation equation = new FIfEquation(EquationType.NORMAL, thenClauses, ifExp, new Opt<FIfWhenElseEquation>(elseClause));
230                equation.setIsTempAssign();
231                s.add(equation);
232            }
233            s.add(thenVars);
234        }
235    }
236   
237    private boolean FIfWhenElseEquation.isTempAssign = false;
238    public void FIfWhenElseEquation.setIsTempAssign() { isTempAssign = true; }
239    public boolean FIfWhenElseEquation.isTempAssign() { return isTempAssign; }
240   
241    public void FIfExp.createArrayTemporariesIfBranch(FExp guard, Scalarizer s) {
242        if (guard == null) {
243            getIfExp().createArrayTemporaries(s);
244        } else {
245            getIfExp().createArrayTemporariesIfBranch(guard.treeCopyNoTransform(), s);
246        }
247        FExp ifExp = getIfExp().scalarize(s);
248        FExp thenGuard = ifExp.treeCopyNoTransform();
249        FExp elseGuard = new FNotExp(ifExp.treeCopyNoTransform());
250        if (guard != null) {
251            thenGuard = new FAndExp(guard.treeCopyNoTransform(), thenGuard);
252            elseGuard = new FAndExp(guard.treeCopyNoTransform(), elseGuard);
253        }
254        getThenExp().createArrayTemporariesIfBranch(thenGuard, s);
255        getElseExp().createArrayTemporariesIfBranch(elseGuard, s);
256    }
257   
258   
259    public void FFunctionCall.createArrayTemporaries(Scalarizer s) {
260        // No names available as a function call arg.
261        boolean b = !extractTemp(s);
262        if (b)
263            s.getNames().addLayer(0);
264        super.createArrayTemporaries(s);
265        if (b)
266            s.getNames().removeLayer();
267    }
268   
269    public void FRecordConstructor.createArrayTemporaries(Scalarizer s) {
270        // No names available as record con arg.
271        boolean b = !extractTemp(s);
272        if (b)
273            s.getNames().addLayer(0);
274        super.createArrayTemporaries(s);
275        if (b)
276            s.getNames().removeLayer();
277    }
278   
279    public void FSizeExp.createArrayTemporaries(Scalarizer s) {
280        boolean b = !extractTemp(s);
281        if (b) {
282            s.getNames().addLayer(0);
283        }
284        if (extractTemp(s)) {
285            knownArrayTemporaries(s);
286        } else {
287            createArrayTemporariesInChildren(s);
288        }
289        if (b) {
290            s.getNames().removeLayer();
291        }
292    }
293   
294    public void FSizeExp.createArrayTemporariesInChildren(Scalarizer s) {
295        if (!isArray() && (getFExp().isSlice() || !getFExp().size().isUnknown(dimension()))) {
296            getFExp().size().createArrayTemporaries(s, dimension());
297        } else {
298            if (isArray()) {
299                getArray().createArrayTemporaries(s);
300            } else {
301                super.createArrayTemporariesInChildren(s);
302            }
303        }
304    }
305   
306    public void Size.createArrayTemporaries(Scalarizer s, int i) {
307       
308    }
309   
310    @Override
311    public void MutableSize.createArrayTemporaries(Scalarizer s, int i) {
312        if (exps[i] != null) {
313            exps[i].createArrayTemporaries(s);
314        } else {
315            super.createArrayTemporaries(s, i);
316        }
317    }
318   
319
320    /**
321     * Create clauses for and replace this known size expression with a temp variable.
322     * Used in both functions and equations.
323     * @param s Scalarization visitor
324     */
325    public void FExp.knownArrayTemporaries(Scalarizer s) {
326        s.addTempVar(this, true);
327        Array arr = getArray();
328        for (Index i : indices()) {
329            arr.get(i).createArrayTemporaries(s);
330            s.add(tempExp(i), arr.get(i).scalarize(s));
331        }
332        useTempVar = true;
333    }
334   
335    @Override
336    public void FAbstractFunctionCall.knownArrayTemporaries(Scalarizer s) {
337        if (scalarizeAsFunctionCallClause()) {
338            createArrayTemporariesInChildren(s);
339            List<FFunctionCallLeft> lefts = new List<>();
340            if (isFunctionCallClause()) {
341                for (FFunctionCallLeft left : myLefts()) {
342                    lefts.add(left.scalarize(s));
343                }
344                useTempVar = true;
345            } else {
346                s.addTempVar(this, true);
347                useTempVar = true;
348                lefts.add(new FFunctionCallLeft(new Opt<FExp>(scalarize(s))));
349            }
350            s.add(lefts, (FAbstractFunctionCall)scalarizeExp(s));
351        } else {
352            super.knownArrayTemporaries(s);
353        }
354    }
355   
356    syn boolean FAbstractFunctionCall.scalarizeAsFunctionCallClause() = false;
357    eq FFunctionCall  .scalarizeAsFunctionCallClause() = true;
358    eq FSpatialDistExp.scalarizeAsFunctionCallClause() = isFunctionCallClause();
359   
360    public FFunctionCallLeft FFunctionCallLeft.scalarize(Scalarizer s) {
361        if (hasFExp()) {
362            return getFExp().scalarizeLeft(s);
363        } else {
364            return new FFunctionCallLeft();
365        }
366    }
367   
368    public FFunctionCallLeft FExp.scalarizeLeft(Scalarizer s) {
369        if (size().isEmpty()) {
370            return new FFunctionCallLeft();
371        }
372       
373        FExp exp = this;
374        if (isSlice() && !s.unroll()) {
375            s.addTempVar(exp, true);
376            exp = exp.tempExp();
377            exp = exp.scalarizeExp(s);
378        } else if (!s.inFunction() || isSlice()) {
379            exp = type().createRecordConstructor(s, exp);
380        } else {
381            exp = exp.scalarizeExp(s);
382        }
383        return new FFunctionCallLeft(new Opt<FExp>(exp));
384    }
385   
386    @Override
387    public void FFunctionCallLeft.createArrayTemporaries(Scalarizer s) {
388        if (hasFExp()) {
389            getFExp().createArrayTemporaries(s);
390            if (getFExp().isSlice() && !s.unroll()) {
391                type().scalarizeAssignment((Scalarizer.Algorithm)s, (FAssignableExp)getFExp(), getFExp().tempExp());
392            }
393        }
394    }
395   
396    public void FVectorFunctionCall.knownArrayTemporaries(Scalarizer s) {
397        getArray().createArrayTemporaries(s);
398    }
399   
400    /**
401     * Create clauses for and replace this unknown size expression with a temp variable.
402     * Used in functions.
403     * @param s Scalarization visitor
404     */
405    public void FExp.unknownFunctionArrayTemporaries(Scalarizer s) {
406        s.addTempVar(this, false);
407        createArrayTemporariesInChildren(s);
408        useTempVar = false;
409        type().scalarizeAssignment((Scalarizer.Algorithm)s, tempExp(), this);
410        indexNames = null;
411    }
412
413    public void FAbstractFunctionCall.unknownFunctionArrayTemporaries(Scalarizer s) {
414        if (scalarizeAsFunctionCallClause()) {
415            knownArrayTemporaries(s);
416        } else {
417            super.unknownFunctionArrayTemporaries(s);
418        }
419    }
420   
421    public void FVectorFunctionCall.unknownFunctionArrayTemporaries(Scalarizer s) {
422        s.addTempVar(this, true);
423        List<FExp> newArgs = new List<FExp>();
424        List<FStatement> result = new List<FStatement>();
425        List<FStatement> outer = s.getClauses();
426        ForNames names = s.getNames();
427
428        names.addLayer(ndims());
429        names.fillLayer(this);
430
431        List<FStatement> firstLoop = new List<FStatement>();
432        FAccessExp funcLeft = tempExp(names.createFArraySubscripts(1));
433
434        for (int i = 0; i < getNumArg(); ++i) {
435            FExp arg = getArg(i);
436
437            arg.createArrayTemporaries(s.block(outer));
438
439            if (getVectorized()[i]) {
440                arg.addArrayUsesToIndexMap(s);
441                int dimDiff = arg.ndims() - ndims();
442
443                if (dimDiff > 0) {
444                    names.addLayer(dimDiff + 1);
445                    names.promote(0);
446                    names.fillLayer(arg);
447                   
448                    String tempName = arg.calcTempVarName();
449                    FAccessExp tempExp = new FAccessExp(new FAccessString(tempName));
450
451                    FType tempType = arg.type().arrayType(arg.size().contract(1));
452                    s.block(firstLoop).addTempVar(tempType, tempName, true, true);
453
454                    newArgs.add(tempExp(tempName, names.createFArraySubscripts(0, dimDiff - 1)));
455
456                    FAssignableExp left = tempExp(tempName, names.createFArraySubscripts(1, dimDiff + 1));
457                    FExp right = arg.tempExp(names.createFArraySubscripts(0, dimDiff + 1));
458                    List<FStatement> inner = new List<FStatement>();
459                    inner.add(new FAssignStmt(left, right));
460                    names.createForLoops(s, firstLoop, inner, arg.size(), 1, dimDiff + 1);
461                    names.removeLayer();
462                } else {
463                    newArgs.add(arg.scalarize(s));
464                }
465            } else {
466                newArgs.add(arg.scalarize(s));
467            }
468        }
469
470        FFunctionCall funcRight = new FFunctionCall(getName().fullCopy(), newArgs, getFType().scalarType());
471        firstLoop.add(new FAssignStmt(funcLeft, funcRight));
472
473        names.createForLoops(s, outer, firstLoop, size(), 0, 1);
474        names.removeLayer();
475    }
476   
477    public void FArray.unknownFunctionArrayTemporaries(Scalarizer s) {
478        s.addTempVar(this, true);
479        ForNames names = s.getNames();
480        boolean iter = isIterArray();
481        names.addLayer(ndims()- (iter ? 0 : 1));
482        names.fillLayer(this);
483
484        for (int i = 0; i < getNumFExp(); i++) {
485            List<FStatement> inner = new List<FStatement>();
486            List<FStatement> outer = s.getClauses();
487            FExp right = getFExp(i);
488            FAccessExp left;
489            if (iter) {
490                left = tempExp(names.createFArraySubscripts());
491                getFExp(0).editNamesIter(s);
492                right.createArrayTemporaries(s.block(inner));
493                right.addArrayUsesToIndexMap(s);
494                names.removeLayer();
495                right = ((FIterExp) right).getFExp();
496            } else {
497                List<FSubscript> subs = new List<FSubscript>();
498                subs.add(new FIntegerSubscript(i+1));
499                if (names.hasNames()) {
500                    subs.addAll(names.createFArraySubscripts().copyAsFArrayExpSubscripts().getFSubscriptListNoTransform());
501                }
502                left = tempExp(new FArrayExpSubscripts(subs));
503                right.createArrayTemporaries(s);
504                right.addArrayUsesToIndexMap(s);
505            }
506            type().scalarizeAssignment_sub((Scalarizer.Algorithm)s.block(inner), left, right);
507            s.createForLoops(inner, getFExp(i));
508        }
509
510        names.removeLayer();
511    }
512   
513    public void FMulExp.unknownFunctionArrayTemporaries(Scalarizer s) {
514        s.addTempVar(this, true);
515        if (isElementWise()) {
516            unknownFunctionArrayTemporariesElementWise(s);
517        } else {
518            unknownFunctionArrayTemporariesMatrix(s);
519        }
520    }
521   
522    public void FMulExp.unknownFunctionArrayTemporariesMatrix(Scalarizer s) {
523        ForNames names = s.getNames();
524        FAccessExp sum = new FAccessExp(calcTempVarName());
525        s.addTempVar(type().scalarType(), sum.name(), true, true);
526       
527        names.addLayer(ndims());
528        names.fillLayer(this);
529       
530        // Set up indices for the left operand
531        FExp exp = getLeft();
532        names.addLayer(exp.ndims());
533        if (names.size() > 1)
534            names.promote(0);
535        String i = names.create(this);
536       
537        // Scalarize left operand
538        exp.createArrayTemporaries(s);
539        exp.addArrayUsesToIndexMap(s);
540        FExp left = exp.scalarize(s);
541        names.removeLayer();
542       
543        // Set up indices and scalarize the right operand
544        exp = getRight();
545        names.addLayer(exp.ndims());
546        names.add(i);
547        if (names.size() > 1)
548            names.promote(ndims() - 1);
549        exp.createArrayTemporaries(s);
550        exp.addArrayUsesToIndexMap(s);
551        FExp right = exp.scalarize(s);
552        names.removeLayer();
553       
554        // Add statement updating temp var to loop
555        FExp mul = new FMulExp(left, right);
556        FExp add = new FAddExp(sum.fullCopy(), mul);
557        List<FStatement> inner = new List<FStatement>();
558        inner.add(new FAssignStmt(sum.fullCopy(), add));
559       
560        // Create inner loop
561        FForStmt fs = new FForStmt(new FForIndex(i, getRight().size().createFExp(0)), inner);
562       
563        // Create outer loops
564        List<FStatement> outer = new List<FStatement>();
565        outer.add(new FAssignStmt(sum, type().scalarType().zeroLiteral()));
566        outer.add(fs);
567        outer.add(new FAssignStmt(tempExp(names.createFArraySubscripts()), sum.fullCopy()));
568       
569        s.createForLoops(outer, this);
570       
571        names.removeLayer();
572    }
573   
574    public void FMulExp.unknownFunctionArrayTemporariesElementWise(Scalarizer s) {
575        ForNames names = s.getNames();
576        FAccessExp sum = new FAccessExp(calcTempVarName());
577        s.addTempVar(type().scalarType(), sum.name(), true, true);
578       
579        names.addLayer(ndims());
580        names.fillLayer(this);
581       
582        FExp left = getLeft();
583        left.createArrayTemporaries(s);
584        left.addArrayUsesToIndexMap(s);
585        left = left.scalarize(s);
586       
587        FExp right = getRight();
588        right.createArrayTemporaries(s);
589        right.addArrayUsesToIndexMap(s);
590        right = right.scalarize(s);
591       
592        List<FStatement> inner = new List<>();
593        FAccessExp temp = tempExp(names.createFArraySubscripts());
594        FExp mul = dynamicFExp(new FMulExp(left, right));
595        type().scalarizeAssignment_sub((Scalarizer.Algorithm)s.block(inner), temp, mul);
596        s.createForLoops(inner, this);
597       
598        names.removeLayer();
599    }
600   
601    public void FAbstractCat.unknownFunctionArrayTemporaries(Scalarizer s) {
602        s.addTempVar(this, true);
603        ForNames names = s.getNames();
604        int catDim  = dimension();
605        FExp offset = new FIntegerLitExp(0);
606        FExp firstArg = getFExp(0);
607        ForNames orig = names.copySurface();
608       
609        for (FExp exp : getFExps()) {
610            names.addLayer(exp.ndims());
611            names.fillLayer(exp);
612           
613            exp.createArrayTemporaries(s);
614            exp.addArrayUsesToIndexMap(s);
615           
616            FArrayExpSubscripts fas = names.createFArraySubscripts(ndims());
617            FExp ind = fas.getFSubscript(catDim).createFExp();
618            ind = new FAddExp(ind, offset.fullCopy());
619            fas.setFSubscript(new FExpSubscript(ind), catDim);
620           
621            s.createForLoops(tempExp(fas), exp.scalarize(s), exp);
622            names.removeLayer();
623           
624            offset = new FAddExp(offset, exp.size().has(catDim) ? exp.size().createFExp(catDim) : new FIntegerLitExp(1));
625        }
626    }
627   
628    public void FAbstractDiagonal.unknownFunctionArrayTemporaries(Scalarizer s) {
629        s.addTempVar(this, true);
630        ForNames names = s.getNames();
631        names.addLayer(ndims());
632        names.fillLayer(this);
633       
634        getFExp().createArrayTemporaries(s);
635        getFExp().addArrayUsesToIndexMap(s);
636       
637        FIfExp right = new FIfExp(
638                new FEqExp(new FAccessExp(names.get(0)), new FAccessExp(names.get(1))),
639                scalarizeDiagonalElement(s),
640                new FIntegerLitExp(0)
641        );
642        s.createForLoops(tempExp(names.createFArraySubscripts(ndims())), right, this);
643        names.removeLayer();
644    }
645   
646    syn FExp FAbstractDiagonal.scalarizeDiagonalElement(Scalarizer s);
647    eq FIdentity.scalarizeDiagonalElement(Scalarizer s) = new FIntegerLitExp(1);
648    eq FDiagonal.scalarizeDiagonalElement(Scalarizer s) = getFExp().scalarize(s);
649   
650    public void FVectorExp.unknownFunctionArrayTemporaries(Scalarizer s) {
651        s.addTempVar(this, true);
652        ForNames names = s.getNames();
653        names.addLayer(getFExp().ndims());
654        names.fillLayer(getFExp());
655       
656        getFExp().createArrayTemporaries(s);
657        getFExp().addArrayUsesToIndexMap(s);
658       
659        FExp ind = null;
660        for (int i = 0; i < names.size(); i++) {
661            FAccessExp u = new FAccessExp(names.get(i));
662            FSubExp u1 = new FSubExp(u, new FIntegerLitExp(1));
663            if (ind != null) {
664                ind = new FMulExp(ind, getFExp().size().createFExp(i));
665                ind = new FAddExp(ind, u1);
666            } else {
667                ind = u1;
668            }
669        }
670        if (ind == null) {
671            ind = new FIntegerLitExp(1);
672        } else {
673            ind = new FAddExp(ind, new FIntegerLitExp(1));
674        }
675       
676        FArrayExpSubscripts fas = new FArrayExpSubscripts();
677        fas.addFSubscript(new FExpSubscript(ind));
678
679        FExp right = getFExp().scalarize(s);
680
681        s.createForLoops(tempExp(fas), right, getFExp());
682        names.removeLayer();
683    }
684   
685    public void FMatrixExp.unknownFunctionArrayTemporaries(Scalarizer s) {
686        s.addTempVar(this, true);
687        ForNames names = s.getNames();
688        names.addLayer(getFExp().ndims());
689        names.fillLayer(getFExp());
690       
691        getFExp().createArrayTemporaries(s);
692        getFExp().addArrayUsesToIndexMap(s);
693
694        s.createForLoops(tempExp(names.createFArraySubscripts(2)), getFExp().scalarize(s), getFExp());
695        names.removeLayer();
696    }
697
698    public void FReductionExp.unknownFunctionArrayTemporaries(Scalarizer s) {
699        s.addTempVar(this, true);
700        unknownReductionSub(s, getFExp());
701    }
702
703    public void FMinMaxExp.unknownFunctionArrayTemporaries(Scalarizer s) {
704        s.addTempVar(this, true);
705        unknownReductionSub(s, getX());
706    }
707
708    public void FCross.unknownFunctionArrayTemporaries(Scalarizer s) {
709        s.addTempVar(this, true);
710        createArrayTemporariesInChildren(s);
711        FExp x = getX();
712        FExp y = getY();
713        for (Index i : indices()) {
714            int j = i.first() % 3 + 1;
715            int k = j % 3 + 1;
716            FExp m1 = new FMulExp(x.extractArrayCell(s, j), y.extractArrayCell(s, k));
717            FExp m2 = new FMulExp(x.extractArrayCell(s, k), y.extractArrayCell(s, j));
718            s.add(tempExp(i), new FSubExp(m1, m2));
719        }
720    }
721
722    public void FSkew.unknownFunctionArrayTemporaries(Scalarizer s) {
723        s.addTempVar(this, true);
724        createArrayTemporariesInChildren(s);
725       
726        FExp inner = getFExp();
727        for (Index i : indices()) {
728            /* Result is:
729             * [    0, -x[3],  x[2];
730             *   x[3],     0, -x[1];
731             *  -x[2],  x[1],     0 ]
732             */
733            FExp cell = null;
734            int j = 6 - i.get(0) - i.get(1);
735            switch ((i.get(0) - i.get(1) + 2) % 3) {
736            case 0:
737                cell = inner.extractArrayCell(s, j);
738                break;
739            case 1:
740                cell = inner.extractArrayCell(s, j);
741                cell = new FNegExp(cell);
742                break;
743            case 2:
744                cell = new FIntegerLitExp(0);
745                break;
746            }
747            s.add(tempExp(i), cell);
748        }
749    }
750
751    public void FSymmetric.unknownFunctionArrayTemporaries(Scalarizer s) {
752        s.addTempVar(this, true);
753        createArrayTemporariesInChildren(s);
754        FExp exp = getFExp();
755       
756        ForNames names = s.getNames();
757        names.addLayer(2);
758        names.fillLayer(this);
759       
760        FAccessExp left = tempExp(names.createFArraySubscripts());
761        FExp[] ijs = names.createFExpArray();
762        FExp expIJ = exp.extractArrayCell(s, ijs);
763        names.createTransposedLayer();
764        FExp expJI = exp.extractArrayCell(s, names.createFExpArray());
765        names.removeLayer();
766        FExp right = new FIfExp(new FLeqExp(ijs[0], ijs[1]), expIJ, expJI);
767       
768        List<FStatement> inner = new List<FStatement>();
769        right = dynamicFExp(right);
770        type().scalarizeAssignment_sub((Scalarizer.Algorithm)s.block(inner), left, right);
771        s.createForLoops(inner, exp);
772        names.removeLayer();
773    }
774
775    public void FOuterProduct.unknownFunctionArrayTemporaries(Scalarizer s) {
776        s.addTempVar(this, true);
777        createArrayTemporariesInChildren(s);
778       
779        ForNames names = s.getNames();
780        names.addLayer(2);
781        names.fillLayer(this);
782       
783        FAccessExp left = tempExp(names.createFArraySubscripts());
784        FExp[] ijs = names.createFExpArray();
785        FExp x = getX().extractArrayCell(s, ijs[0]);
786        FExp y = getY().extractArrayCell(s, ijs[1]);
787        FExp right = new FMulExp(x, y);
788       
789        List<FStatement> inner = new List<FStatement>();
790        right = dynamicFExp(right);
791        type().scalarizeAssignment_sub((Scalarizer.Algorithm)s.block(inner), left, right);
792        s.createForLoops(inner, this);
793        names.removeLayer();
794    }
795   
796    syn FAssignableExp FBuiltInFunctionCall.reducerTempExp(Scalarizer s) = type().isArray() ? 
797            tempExp(s.getNames().createFArraySubscripts(ndims())) : tempExp();
798   
799    syn FExp FBuiltInFunctionCall.scalarReduceExp(FExp reducer,  FExp scalar) = null;
800    eq FSumExp.scalarReduceExp(FExp reducer,     FExp scalar) = new FAddExp(reducer, scalar);
801    eq FProductExp.scalarReduceExp(FExp reducer, FExp scalar) = new FMulExp(reducer, scalar);
802    eq FMaxExp.scalarReduceExp(FExp reducer, FExp scalar) =
803            new FIfExp(new FGtExp(reducer, scalar.treeCopy()), reducer.treeCopy(), scalar.treeCopy());
804    eq FMinExp.scalarReduceExp(FExp reducer, FExp scalar) =
805            new FIfExp(new FLtExp(reducer, scalar.treeCopy()), reducer.treeCopy(), scalar.treeCopy());
806   
807    protected void FBuiltInFunctionCall.unknownReductionSub(Scalarizer s, FExp exp) {
808        ForNames names = s.getNames();
809        List<FStatement> clauses = s.getClauses();
810
811        names.addLayer(exp.ndims());
812        names.fillLayer(this);
813
814        List<FStatement> inner = new List<FStatement>();
815        List<FStatement> mid   = new List<FStatement>();
816        boolean iter = exp.editNamesIter(s);
817        if (iter) {
818            exp.createArrayTemporaries(s.block(inner));
819        } else {
820            exp.createArrayTemporaries(s.block(mid));
821        }
822        exp.addArrayUsesToIndexMap(s);
823        if (iter) {
824            names.removeLayer();
825        }
826
827        mid.add(new FAssignStmt(reducerTempExp(s), scalarReduceStartValue().buildLiteral()));
828        inner.add(new FAssignStmt(reducerTempExp(s), scalarReduceExp(reducerTempExp(s), exp.scalarize(s))));
829
830        names.createForLoops(s, mid, inner, exp.size(), ndims(), exp.ndims());
831        names.createForLoops(s, clauses, mid, exp.size(), 0, ndims());
832        names.removeLayer();
833    }
834   
835    /**
836     * Helper for unknown size expressions containing iteration expressions.
837     */
838    public boolean FExp.editNamesIter(Scalarizer s) {
839        return false;
840    }
841    public boolean FIterExp.editNamesIter(Scalarizer s) {
842        ForNames names = s.getNames();
843        int i = 0;
844        for (; i < getNumForIndex(); i++) {
845            getForIndex(i).setIndexName(names.get(i));
846        }
847        names.addLayer(getFExp().ndims());
848        for (; i < getFExp().ndims() + getNumForIndex(); i++) {
849            names.promote(i);
850        }
851        return true;
852    }
853
854    private String FForIndex.indexName = null;
855    public void CommonForIndex.setIndexName(String indexName) {}
856    public void FForIndex.setIndexName(String indexName) { this.indexName = indexName; }
857
858    inh String FAbstractVariable.myForIndexName();
859    eq ASTNode.getChild().myForIndexName()       = null;
860    eq FForIndex.getFVariable().myForIndexName() = indexName;
861
862    inh FExp FAbstractVariable.scalarizeIterIndex(Scalarizer s);
863    eq FForIndex.getFVariable().scalarizeIterIndex(Scalarizer s) = 
864        indexName == null ? null : getFExp().scalarizeWithIndex(s, new FAccessExp(indexName));
865    eq ASTNode  .getChild()    .scalarizeIterIndex(Scalarizer s) = null;
866
867    public FExp FExp.scalarizeWithIndex(Scalarizer s, FExp res) {
868        return null;
869    }
870
871    public FExp FRangeExp.scalarizeWithIndex(Scalarizer s, FExp res) {
872        boolean startIsOne = getFExp(0).isIntegerLiteral(1);
873        if (!startIsOne || hasStep()) {
874            res = new FSubExp(res, new FIntegerLitExp(1));
875            if (hasStep())
876                res = new FMulExp(res, getFExp(1).scalarize(s));
877            res = new FAddExp(getFExp(0).scalarize(s), res);
878        }
879        return res;
880    }
881
882    /**
883     * Wrapper for {@link ASTNode#addArrayUsesToIndexMap(Scalarizer s, FExp[] names)}.
884     */
885    public void ASTNode.addArrayUsesToIndexMap(Scalarizer s) {
886        if (s.getNames().size() > 0) {
887            addArrayUsesToIndexMap(s, s.getNames().createFExpArray());
888        }
889    }
890   
891    /**
892     * Traverser for {@link FExp#addArrayUsesToIndexMap(FExp[] names)}.
893     */
894    public void ASTNode.addArrayUsesToIndexMap(Scalarizer s, FExp[] names) {
895        for (ASTNode n : this)
896            n.addArrayUsesToIndexMap(s, names);
897    }
898   
899    /**
900     * Copies top layer in <code>names</code> to id uses and creates entries
901     * in <code>indexNames</code> for expressions replaced with temps.
902     */
903    public void FExp.addArrayUsesToIndexMap(Scalarizer s, FExp[] names) {
904        if (useTempVar) {
905            if (isArray()) {
906                indexNames = names;
907            }
908        } else {
909            super.addArrayUsesToIndexMap(s, names);
910        }
911    }
912   
913    public void FSizeExp.addArrayUsesToIndexMap(Scalarizer s, FExp[] names) {
914        if (useTempVar() && isArray()) {
915            indexNames = names;
916        }
917    }
918   
919    public void FAccessExp.addArrayUsesToIndexMap(Scalarizer s, FExp[] names) {
920        if (!hasFArraySubscripts() && myFV().isArray()) {
921            indexNames = names;
922        }
923        super.addArrayUsesToIndexMap(s, names);
924    }
925   
926    public void CommonAccess.addArrayUsesToIndexMap(Scalarizer s, FExp[] names) {
927        if (isArray()) {
928            int i = 0;
929            for (FArraySubscripts fas : allFArraySubscripts()) {
930                i = fas.addArrayUsesToIndexMap(s, names, i);
931            }
932        }
933    }
934
935    public int FArraySubscripts.addArrayUsesToIndexMap(Scalarizer s, FExp[] names, int i) { return i; }
936    public int FArrayExpSubscripts.addArrayUsesToIndexMap(Scalarizer s, FExp[] names, int i) {
937        for (FSubscript fs : getFSubscripts()) {
938            if (fs.ndims() > 0) {
939                FExp[] indexNames = new FExp[1];
940                indexNames[0] = names[i];
941                fs.addArrayUsesToIndexMap(s, indexNames);
942                i++;
943            }
944        }
945        return i;
946    }
947
948    public void FTempAccessExp.addArrayUsesToIndexMap(Scalarizer s, FExp[] names) {
949        indexNames = names;
950    }
951
952    public void FRangeExp.addArrayUsesToIndexMap(Scalarizer s, FExp[] names) {
953        indexNames = names;
954        super.addArrayUsesToIndexMap(s, names);
955    }
956
957    public void FLinspace.addArrayUsesToIndexMap(Scalarizer s, FExp[] names) {
958        indexNames = names;
959        super.addArrayUsesToIndexMap(s,names);
960    }
961
962    public void FColonSubscript.addArrayUsesToIndexMap(Scalarizer s, FExp[] names) {
963        indexName = names[0];
964    }
965
966    public void FTranspose.addArrayUsesToIndexMap(Scalarizer s, FExp[] names) {
967        FExp[] local = names.clone();
968        local[0] = names[1];
969        local[1] = names[0];
970        super.addArrayUsesToIndexMap(s, local);
971    }
972
973    public void FFunctionCall.addArrayUsesToIndexMap(Scalarizer s, FExp[] names) {
974        // No names available as a function call arg.
975        if (extractTemp(s)) {
976            super.addArrayUsesToIndexMap(s, names);
977        }
978    }
979
980    public void FRecordConstructor.addArrayUsesToIndexMap(Scalarizer s, FExp[] names) {
981        // No names available as record con arg.
982        if (extractTemp(s)) {
983            super.addArrayUsesToIndexMap(s, names);
984        }
985    }
986
987}
988
989aspect FunctionScalarizationHelpers {
990   
991    /**
992     * A node that can look up variable names in the flat tree.
993     */
994    public interface FlatLookupNode {
995        public FAbstractVariable lookupFV(String name);
996    }
997    FFunctionVariable implements FlatLookupNode;
998    FExp implements FlatLookupNode;
999
1000    inh FAbstractVariable FFunctionVariable.lookupFV(String name);
1001    inh FAbstractVariable FExp.lookupFV(String name);
1002
1003    /**
1004     * Creates and organizes names of for indices for generated for loops.
1005     */
1006    public class ForNames implements Iterable<String> {
1007        private ArrayList<String[]> names;
1008        private ArrayList<Integer> last;
1009        private int pos;
1010       
1011        /**
1012         * Standard constructor.
1013         */
1014        public ForNames() {
1015            names = new ArrayList<String[]>();
1016            last = new ArrayList<Integer>();
1017            last.add(0);
1018        }
1019       
1020        /**
1021         * Creates a new ForNames with a single layer with space for <code>n</code> names.
1022         */
1023        public ForNames(int n) {
1024            this();
1025            addLayer(n);
1026        }
1027       
1028        /**
1029         * Add a new layer of names, that can be filled with new names or names
1030         *        from the layer underneath.
1031         *
1032         * @param n  the number of names in the new layer
1033         */
1034        public void addLayer(int n) {
1035            names.add(new String[n]);
1036            pos = 0;
1037            last.add(last());
1038        }
1039       
1040        /**
1041         * Fills all empty spots in the top layer with newly created names.
1042         */
1043        public void fillLayer(FlatLookupNode context) {
1044            String[] top = topLayer();
1045            for (int i = pos; i < top.length; i++) 
1046                create(context);
1047        }
1048       
1049        /**
1050         * Removes the top layer, exposing the layer underneath.
1051         */
1052        public void removeLayer() {
1053            names.remove(names.size() - 1);
1054            last.remove(last.size() - 1);
1055        }
1056
1057        private String[] topLayer() {
1058            return names.get(names.size() - 1);
1059        }
1060       
1061        public boolean hasNames() {
1062            return names.size() > 0 && topLayer().length > 0;
1063        }
1064       
1065        /**
1066         * Gets name with index <code>i</code> in the top layer.
1067         */
1068        public String get(int i) {
1069            return topLayer()[i];
1070        }
1071       
1072        /**
1073         * Adds a name to the top layer.
1074         */
1075        public void add(String name) {
1076            topLayer()[pos++] = name;
1077        }
1078       
1079        /**
1080         * Creates a new name and adds it to the top layer.
1081         *
1082         * @return the created name
1083         */
1084        public String create(FlatLookupNode context) {
1085            String name;
1086            int l = last();
1087            do {
1088                name = "i" + (++l);
1089            } while (context != null && !context.lookupFV(name).isUnknown()); 
1090            add(name);
1091            last.set(last.size()-1, l);
1092            return name;
1093        }
1094       
1095        private int last() {
1096            return last.get(last.size()-1);
1097        }
1098       
1099        /**
1100         * Adds a name from the underlying layer to the top layer.
1101         *
1102         * @param i  the index in the underlying layer
1103         */
1104        public void promote(int i) {
1105            add(names.get(names.size() - 2)[i]);
1106        }
1107       
1108        /**
1109         * Checks if there are enough layers to promote a name.
1110         */
1111        public boolean canPromote() {
1112            return names.size() > 1;
1113        }
1114       
1115        /**
1116         * Return the number of names in the top layer.
1117         */
1118        public int size() {
1119            return topLayer().length;
1120        }
1121       
1122        /**
1123         * Iterates over the top layer.
1124         */
1125        public Iterator<String> iterator() {
1126            return Arrays.asList(topLayer()).iterator();
1127        }
1128       
1129        /**
1130         * Pushes a copy of the top layer with first and second names switched
1131         */
1132        public void createTransposedLayer() {
1133            String[] lay = topLayer();
1134            addLayer(lay.length);
1135            for (int i = 0; i < lay.length; i++) {
1136                promote(i);
1137            }
1138            topLayer()[0] = lay[1];
1139            topLayer()[1] = lay[0];
1140           
1141        }
1142       
1143        /**
1144         * Creates nestled for loops using the top layer of names.
1145         * 
1146         * Adds the outermost for loop to a list of statements.
1147         *
1148         * @param outer  list to add the created for statements to
1149         * @param inner  list of statements put inside the loop
1150         * @param sizes  array of expressions describing the size of each dimension
1151         */
1152        public void createForLoops(List<FStatement> outer, List<FStatement> inner, FExp[] sizes, int startDim) {
1153            if (startDim < sizes.length) {
1154                List<FStatement> mid = new List<FStatement>();
1155                createForLoops(mid, inner, sizes, startDim + 1);
1156                FForIndex ffi = new FForIndex(topLayer()[startDim], sizes[startDim]);
1157                outer.add(new FForStmt(ffi, mid));
1158            } else {
1159                outer.addAll(inner);
1160            }
1161        }
1162       
1163        /**
1164         * Creates nestled for loops over a single variable, using the top layer of names.
1165         * 
1166         * Adds the outermost for loop to a list of statements.
1167         *
1168         * @param outer  list to add the created for statements to
1169         * @param inner  list of statements put inside the loop
1170         * @param var    name of the variable to loop over
1171         */
1172        public void createForLoops(List<FStatement> outer, List<FStatement> inner, FAccess var) {
1173            int n = topLayer().length;
1174            FExp[] sizes = new FExp[n];
1175            for (int i = 0; i < n; i++) {
1176                sizes[i] = new FSizeExp(var, i);
1177            }
1178            createForLoops(outer, inner, sizes, 0);
1179        }
1180
1181        /**
1182         * Creates nestled (from d1 to d2) for loops over an expression,
1183         * using the top layer of names.
1184         * 
1185         * Adds the outermost for loop to a list of statements.
1186         *
1187         * @param outer  list to add the created for statements to
1188         * @param inner  list of statements put inside the loop
1189         * @param exp    expression to loop over
1190         * @param d1     dimensions to start in
1191         * @param d2     dimensions to end in
1192         */
1193        public void createForLoops(Scalarizer s, List<FStatement> outer, List<FStatement> inner, Size size, int d1, int d2) {
1194            FExp[] sizes = new FExp[d2];
1195            for (int i = d1; i < d2; i++) {
1196                sizes[i] = size.scalarize(s, i);
1197            }
1198            createForLoops(outer, inner, sizes, d1);
1199        }
1200       
1201        /**
1202         * Creates nestled for loops over an expression, using the top layer of names.
1203         * 
1204         * Adds the outermost for loop to a list of statements.
1205         *
1206         * @param outer  list to add the created for statements to
1207         * @param inner  list of statements put inside the loop
1208         * @param exp    expression to loop over
1209         */
1210        public void createForLoops(Scalarizer s, List<FStatement> outer, List<FStatement> inner, Size size) {
1211            createForLoops(s, outer, inner, size, 0, size.ndims());
1212        }
1213
1214        /**
1215         * Creates a new FArraySubscripts with uses of the <code>d1</code> to <code>d2</code> names
1216         * in the top layer as subscripts. When out of names, adds 1s.
1217         *
1218         * Returns null if d1 == d2.
1219         */
1220        public FArrayExpSubscripts createFArraySubscripts(int d1, int d2) {
1221            if (d1 == d2) {
1222                return null;
1223            }
1224            FArrayExpSubscripts fas = new FArrayExpSubscripts();
1225            for (int i = d1; i < d2; ++i) {
1226                if (i < topLayer().length) {
1227                    fas.addFSubscript(new FExpSubscript(new FTempAccessExp(new FAccessFull(topLayer()[i]))));
1228                } else {
1229                    fas.addFSubscript(new FIntegerSubscript(1));
1230                }
1231            }
1232            return fas;
1233        }
1234       
1235        /**
1236         * Creates a new FArraySubscripts with uses of the <code>d</code>
1237         * first names in the top layer as subscripts. When out of names, adds 1s.
1238         * Returns null if d == 0.
1239         */
1240        public FArrayExpSubscripts createFArraySubscripts(int d) {
1241            return createFArraySubscripts(0, d);
1242        }
1243       
1244        /**
1245         * Creates a new FArraySubscripts with uses of all the names in the top layer.
1246         * Returns null if no names available.
1247         */
1248        public FArrayExpSubscripts createFArraySubscripts() {
1249            return createFArraySubscripts(topLayer().length);
1250        }
1251
1252        public FExp[] createFExpArray() {
1253            if (!hasNames())
1254                return new FExp[0];
1255            FExp[] subs = new FExp[topLayer().length];
1256            int i = 0;
1257            for (String s : topLayer()) {
1258                subs[i++] = new FAccessExp(s);
1259            }
1260            return subs;
1261        }
1262       
1263        /**
1264         * Creates a new ForNames with the top layer copied
1265         */
1266        public ForNames copySurface() {
1267            ForNames fn = new ForNames();
1268            if (names.size() > 0) {
1269                fn.addLayer(topLayer().length);
1270                for (String s : topLayer())
1271                    fn.add(s);
1272            }
1273            fn.last.add(last());
1274            return fn;
1275        }
1276    }
1277}
Note: See TracBrowser for help on using the repository browser.