source: branches/dev-jw-2590/Compiler/ModelicaMiddleEnd/src/jastadd/structural/DynamicStates.jrag @ 13900

Last change on this file since 13900 was 13900, checked in by jwedin, 6 weeks ago

Changed so that node count dumping is done on the root node instead of statically on ASTNode. Refactored some fields to no longer be static. Changed so that DSSets are given their id in the constructor. #5865

File size: 39.7 KB
Line 
1import java.util.Collections;
2import java.util.Map;
3
4/*
5    Copyright (C) 2015 Modelon AB
6
7    This program is free software: you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation, version 3 of the License.
10
11    This program is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14    GNU General Public License for more details.
15
16    You should have received a copy of the GNU General Public License
17    along with this program.  If not, see <http://www.gnu.org/licenses/>.
18*/
19
20aspect DynamicStateSelect{
21   
22    syn lazy Map<FVariable, DynamicStateSet> DynamicStateManager.varLookupMap() {
23        Map<FVariable, DynamicStateSet> map = new HashMap<FVariable, DynamicStateSet>();
24        for (DynamicStateSet set : getSets()) {
25            for (FVariable var : set.fVars())
26                map.put(var, set);
27        }
28        return map;
29    }
30   
31    syn DynamicStateSet DynamicStateManager.lookupSet(FVariable var) = varLookupMap().get(var);
32
33    syn int DynamicStateSet.numStates() = getNumVar() - numAlgebraics();
34    syn int DynamicStateSet.numAlgebraics() = getNumAlgebraics();
35    syn int DynamicStateSet.numVars() = getNumVar();
36    syn int DynamicStateSet.id() = getSetId();
37
38    syn lazy FVariable[] DynamicStateSet.fVars() {
39        FVariable[] vars = new FVariable[getNumVar()];
40        for (int i = 1; i <= vars.length; i++)
41            vars[i - 1] = getVar(i - 1).myFV().asFVariable();
42        return vars;
43    }
44
45    syn lazy Map<FAbstractVariable, Integer> DynamicStateSet.varIndexMap() {
46        Map<FAbstractVariable, Integer> map = new HashMap<FAbstractVariable, Integer>();
47        FVariable[] vars = fVars();
48        for (int i = 1; i <= numVars(); i++)
49            map.put(vars[i - 1], i);
50        return map;
51    }
52
53    syn int DynamicStateSet.varIndex(FAbstractVariable var) = varIndexMap().get(var);
54
55    syn Collection<FVariable> DynamicStateSet.fVarsColl() = Arrays.asList(fVars());
56
57    syn DynamicStateSet FAbstractVariable.dynamicStateSet() = null;
58    eq FVariable.dynamicStateSet() = myFClass().getDynamicStateManager().lookupSet(this);
59   
60    syn int FAbstractVariable.dynamicStateVarIndex() = dynamicStateSet().varIndex(this);
61
62    syn boolean FAbstractVariable.isDynamicState() = dynamicStateSet() != null;
63
64    syn boolean FAbstractVariable.isFDynamicStateVariable() = false;
65    eq FDynamicStateVariable.isFDynamicStateVariable() = true;
66
67    syn FDynamicStateVariable FAbstractVariable.asFDynamicStateVariable() {
68        throw new UnsupportedOperationException("Unable to convert " + getClass().getSimpleName() + " to FDynamicStateVariable!");
69    }
70    eq FDynamicStateVariable.asFDynamicStateVariable() = this;
71
72    syn boolean FAbstractVariable.isFDynamicAlgebraicVariable() = false;
73    eq FDynamicAlgebraicVariable.isFDynamicAlgebraicVariable() = true;
74   
75    syn FDynamicAlgebraicVariable FAbstractVariable.asFDynamicAlgebraicVariable() {
76        throw new UnsupportedOperationException("Unable to convert " + getClass().getSimpleName() + " to FDynamicAlgebraicVariable!");
77    }
78    eq FDynamicAlgebraicVariable.asFDynamicAlgebraicVariable() = this;
79   
80    syn boolean FVarRefExp.isDynamicState() = false;
81    eq FAccessExp.isDynamicState() = myFV().isDynamicState();
82    eq FDSRefExp.isDynamicState() = true;
83
84    eq FDynamicAlgebraicVariable.bltDependencyVars() = getSet().fVarsColl();
85
86    inh boolean FAccessExp.shouldRewriteToDSRef();
87    eq BaseNode.getChild().shouldRewriteToDSRef()        = true;
88    eq DynamicStateSet.getChild().shouldRewriteToDSRef() = false;
89    eq FDSRefExp.getChild().shouldRewriteToDSRef()       = false;
90
91    private boolean FAccessExp.dynamicStateRewriteEnabled = false;
92    public void ASTNode.enableDynamicStateRewrite() {
93        for (ASTNode n : this)
94            n.enableDynamicStateRewrite();
95    }
96
97    @Override
98    public void FAccessExp.enableDynamicStateRewrite() {
99        super.enableDynamicStateRewrite();
100        dynamicStateRewriteEnabled = true;
101    }
102
103    rewrite FAccessExp {
104        when (dynamicStateRewriteEnabled && isDynamicState() && shouldRewriteToDSRef()) to FDSRefExp {
105            dynamicStateRewriteEnabled = false;
106            return new FDSRefExp(myFV().dynamicStateSet().id(), this);
107        }
108    }
109
110    syn DynamicStateSet FDSRefExp.mySet() = myFClass().getDynamicStateManager().getSet(getSetId() - 1);
111    syn DynamicStateSet FDSDerExp.mySet() = myFClass().getDynamicStateManager().getSet(getSetId() - 1);
112
113    syn List<FAccessExp> FDSRefExp.getUseList() {
114        DynamicStateSet set = mySet();
115        List<FAccessExp> list = new List<>();
116        for (int i = 1; i <= set.numAlgebraics(); i++)
117            list.add(new FAccessExp("_ds." + set.id() + ".a" + i));
118        return list;
119    }
120
121    @Override
122    public <T extends CommonAccessExp> void FDSRefExp.findCommonAccessExpsInTree(Set<T> set, CommonAccessExpLookupVisitor<T> visitor) {
123        for (FAccessExp exp : getUses())
124            visitor.visit(exp, set);
125        visitor.visit(getOrg(), set);
126    }
127
128    syn List<FExp> FDSDerExp.getUseList() {
129        DynamicStateSet set = mySet();
130        List<FExp> list = new List<FExp>();
131        for (FAccessExp var : set.getVars())
132            list.add(var.diff(TIME));
133        return list;
134    }
135
136    @Override
137    public <T extends CommonAccessExp> void FDSDerExp.findCommonAccessExpsInTree(Set<T> set, CommonAccessExpLookupVisitor<T> visitor) {
138        for (FExp exp : getUses())
139            visitor.visit(exp, set);
140    }
141   
142    private Enumerator DynamicStateManager.idEnumerator = new Enumerator(1);
143    public int DynamicStateManager.nextId() {
144        return idEnumerator.next();
145    }
146
147    syn int DynamicStateSet.numCombinations() {
148        int n = numVars();
149        int k = numStates();
150        if (k > n - k)
151            k = n - k;
152        int r=1;
153        for (int i = 1, j = n; i <= k; i++, j--)
154            r = r * j / i;
155        return r;
156    }
157
158    syn lazy FVariable[][] DynamicStateSet.algebraicCombinations() {
159        Collection<FVariable[]> res = new ArrayList<FVariable[]>();
160        genCombinations(res, numVars(), numAlgebraics(), fVars(), 0, 0, new FVariable[numAlgebraics()]);
161        return res.toArray(new FVariable[res.size()][]);
162    }
163
164    private static void DynamicStateSet.genCombinations(Collection<FVariable[]> res, int n, int k, FVariable[] vars, int min, int index, FVariable[] current) {
165        for (int i = min; i <= n - k + index && i < n; i++) {
166            current[index] = vars[i];
167            if (index == k - 1) {
168                FVariable[] copy = new FVariable[k];
169                System.arraycopy(current, 0, copy, 0, k);
170                res.add(copy);
171            } else {
172                genCombinations(res, n, k, vars, i + 1, index + 1, current);
173            }
174        }
175    }
176   
177    syn lazy FVariable[][] DynamicStateSet.stateCombinations() {
178        FVariable[][] algCombs = algebraicCombinations();
179        FVariable[][] res = new FVariable[algCombs.length][];
180        for (int i = 0; i < res.length; i++) {
181            int j = 0;
182            res[i] = new FVariable[numStates()];
183            Set<FVariable> algs = new HashSet<FVariable>();
184            for (FVariable alg : algCombs[i])
185                algs.add(alg);
186            for (FVariable var : fVars())
187                if (!algs.contains(var))
188                    res[i][j++] = var;
189        }
190        return res;
191    }
192
193    private static FVariable[][] EquationBlockFactory.combineDSCombinations(FVariable[][][] sets, int totalNumVars) {
194        if (sets.length == 1)
195            return sets[0];
196        Collection<FVariable[]> res = new ArrayList<FVariable[]>();
197        combineDSCombinations(sets, res, totalNumVars, new FVariable[totalNumVars], 0, 0);
198        return res.toArray(new FVariable[res.size()][]);
199    }
200
201    private static void EquationBlockFactory.combineDSCombinations(FVariable[][][] sets, Collection<FVariable[]> res, int totalNumVars, FVariable[] current, int set, int offset) {
202        for (int i = 1; i <= sets[set].length; i++) {
203            System.arraycopy(sets[set][i - 1], 0, current, offset, sets[set][i - 1].length);
204            if (sets.length == set + 1) {
205                FVariable[] copy = new FVariable[totalNumVars];
206                System.arraycopy(current, 0, copy, 0, totalNumVars);
207                res.add(copy);
208            } else {
209                combineDSCombinations(sets, res, totalNumVars, current, set + 1, offset + sets[set][i - 1].length);
210            }
211        }
212    }
213
214    public void FClass.applyDynamicStateResult(IndexReductionResult result) {
215        if (result.hasDSFailed()) {
216            warning("Unable to use dynamic states since there are too big sets. Using static states instead");
217            return;
218        }
219        DynamicStateManager manager = getDynamicStateManager();
220        for (IndexReductionBiPGraph.DSSet resSet : result.getDSSets()) {
221            List<FAccessExp> varList = new List<>();
222            for (IndexReductionVar var : resSet.vars) {
223                FVariable fVar = var.getVariable();
224                if (fVar.order() == 1)
225                    varList.add(fVar.getMeIntegrated().createAccessExp());
226                else
227                    varList.add(new FAccessExp(fVar.getFAccess().createDerPrefixedName(fVar.order() - 1)));
228            }
229            List<DynamicStateCoefficient> coffList = new List<DynamicStateCoefficient>();
230            for (int eqn = 0; eqn < resSet.coefficients.length; eqn++) {
231                for (int var = 0; var < resSet.coefficients[eqn].length; var++) {
232                    if (resSet.coefficients[eqn][var] != null)
233                        coffList.add(new DynamicStateCoefficient(eqn, var, resSet.coefficients[eqn][var]));
234                }
235            }
236            DynamicStateSet set = new DynamicStateSet(manager.nextId(), resSet.eqns.size(), varList, coffList, null, null);
237            FDynamicAlgebraicVariable[] algebraicVars = new FDynamicAlgebraicVariable[set.numAlgebraics()];
238            for (int i = 1; i <= set.numAlgebraics(); i++) {
239                FDynamicAlgebraicVariable var = new FDynamicAlgebraicVariable(set, i);
240                algebraicVars[i - 1] = var;
241                addFVariable(var);
242            }
243            set.setAlgebraicVars(algebraicVars);
244            FDynamicStateVariable[] stateVars = new FDynamicStateVariable[set.numStates()];
245            for (int i = 1; i <= set.numStates(); i++) {
246                FDynamicStateVariable var = new FDynamicStateVariable(set, i);
247                stateVars[i - 1] = var;
248                addFVariable(var);
249                addFEquation(new FEquation(new FDerExp(var.createFAccess()), new FDSDerExp(set.id(), i)));
250            }
251            set.setStateVars(stateVars);
252            manager.addSet(set);
253        }
254        enableDynamicStateRewrite();
255    }
256   
257    rewrite FDerExp {
258        when (myFV().isDynamicDerivativeVariable()) to FDynamicDerExp {
259            return new FDynamicDerExp(getFAccess(), getOriginalVariable(), order());
260        }
261    }
262   
263    public class IndexReductionBiPGraph {
264        public static class DSSet {
265            public final Set<IndexReductionEq> eqns = new LinkedHashSet<IndexReductionEq>();
266            public final Set<IndexReductionVar> vars = new LinkedHashSet<IndexReductionVar>();
267            public final int id;
268            public FExp[][] coefficients;
269
270            public DSSet(int id) {
271                this.id = id;
272            }
273           
274            public String toString() {
275                StringBuilder sb = new StringBuilder();
276                sb.append(String.format("Set %d, %d equations and %d variables:\n", id, eqns.size(), vars.size()));
277                sb.append("  Equations:\n");
278                for (IndexReductionEq eqn : eqns)
279                    sb.append("    " + eqn + "\n");
280                sb.append("  Variables:\n");
281                for (IndexReductionVar var : vars)
282                    sb.append("    " + var + "\n");
283                return sb.toString();
284            }
285        }
286       
287    }
288
289    public Set<IndexReductionVar> IndexReductionBiPGraph.computeDynamicStateSets(int dynamicStateLimit, 
290            Map<IndexReductionEq, Map<IndexReductionVar, Coefficient>> coefficientsMatrix, IndexReductionResult result) {
291        if (result.hasDSFailed())
292            return Collections.emptySet();
293        Map<IndexReductionVar, IndexReductionEq> initialMatching = new HashMap<IndexReductionVar, IndexReductionEq>();
294        for (IndexReductionVar var : getVariables())
295            initialMatching.put(var, var.getMatching());
296       
297        Map<IndexReductionVar, IndexReductionEq> tempAssignmentMap = computeTempAssignmentMap();
298       
299        ASTNode.log.verbose(printCoefficientsObj(coefficientsMatrix, false));
300        ASTNode.log.verbose(printCoefficientsObj(coefficientsMatrix, true));
301        Set<DSSet> dsSets = new LinkedHashSet<DSSet>();
302        Map<IndexReductionEq, DSSet> dsLookup = new HashMap<IndexReductionEq, DSSet>();
303        Queue<IndexReductionEq> worklist = new ArrayDeque<IndexReductionEq>();
304        SAP1 sap1 = new SAP1(dsLookup.keySet(), coefficientsMatrix);
305        SAP2 sap2 = new SAP2(dsLookup.keySet(), coefficientsMatrix, worklist);
306        for (IndexReductionEq eqn : getEquations()) {
307            Map<IndexReductionVar, Coefficient> coefficients = coefficientsMatrix.get(eqn);
308            if (coefficients == null)
309                continue;
310            Coefficient coff = coefficients.get(eqn.getMatching());
311            if (coff != null && coff.state == COEFFICIENT_STATE.CONTINUOUS)
312                worklist.add(eqn);
313        }
314
315        Enumerator enumerator = new Enumerator();
316        while (!worklist.isEmpty()) {
317            IndexReductionEq eqn = worklist.poll();
318            ASTNode.log.debug("Looking for DS in %s", eqn);
319            Map<IndexReductionVar, Coefficient> coefficients = coefficientsMatrix.get(eqn);
320            if (coefficients == null)
321                continue;
322            if (!dynamicSetCandidate(eqn, eqn.getMatching(), coefficients))
323                continue;
324            lightReset();
325            ASTNode.log.debug("  SAP1");
326            if (sap1.augmentingPath(eqn)) {
327                continue;
328            }
329            DSSet set = dsLookup.get(eqn);
330            if (set == null)
331                set = new DSSet(enumerator.next());
332            Collection<IndexReductionEq> otherEqns = new ArrayList<IndexReductionEq>();
333            ASTNode.log.debug("    Path not found, set %d", set.id);
334            for (IndexReductionVar var : eqn.getVariablesSortedSAP2(tempAssignmentMap)) {
335                if (!dynamicSetCandidate(eqn, var, coefficients))
336                    continue;
337                ASTNode.log.debug("  Checking ncc variable %s", var);
338                if (var.getMatching() == eqn) {
339                    set.vars.add(var);
340                    ASTNode.log.debug("    adding %s to set %d", var, set.id);
341                } else if (var.getMatching() == null) {
342                    set.vars.add(var);
343                    var.setMatching(eqn);
344                    ASTNode.log.debug("    adding %s to set %d", var, set.id);
345                } else {
346                    IndexReductionEq tmpAssignEqn = tempAssignmentMap.get(var);
347                    if (tmpAssignEqn != null) {
348                        if (tmpAssignEqn.getMatching() != var && dsLookup.get(tmpAssignEqn) == null) {
349                            set.vars.add(tmpAssignEqn.getMatching());
350                            set.eqns.add(tmpAssignEqn);
351                            continue;
352                        }
353                    }
354                    lightReset();
355                    DSSet otherSet = dsLookup.get(var.getMatching());
356                    Collection<IndexReductionVar> noVisit = new ArrayList<IndexReductionVar>();
357                    if (otherSet != null)
358                        noVisit.addAll(otherSet.vars);
359                    noVisit.addAll(set.vars);
360                    noVisit.add(eqn.getMatching());
361                    noVisit.add(var);
362                    ASTNode.log.debug("    SAP2 %s", var.getMatching());
363                    Collection<IndexReductionEq> res = sap2.augmentingPath(var.getMatching(), noVisit);
364                    if (res == sap2.trueValue()) {
365                        ASTNode.log.debug("      Path found");
366                        set.vars.add(var);
367                        var.setMatching(eqn);
368                        ASTNode.log.debug("      adding %s to set %d", var, set.id);
369                    } else {
370                        ASTNode.log.debug("      Path not found");
371                        for (IndexReductionEq resEqn : res)
372                            ASTNode.log.debug("      Adding %s to set.eqns", resEqn);
373                        otherEqns.addAll(res);
374                    }
375                }
376            }
377            if (set.vars.size() >= 2 || set.eqns.size() > 0 || otherEqns.size() > 0) {
378                for (IndexReductionEq otherEqn : otherEqns) {
379                    DSSet otherSet = dsLookup.remove(otherEqn);
380                    if (otherSet != null) {
381                        ASTNode.log.debug("  Merging with set %d from %s", otherSet.id, otherEqn);
382                        dsSets.remove(otherSet);
383                        for (IndexReductionVar memberVar : otherSet.vars) {
384                            set.vars.add(memberVar);
385                            ASTNode.log.debug("    adding %s to set %d", memberVar, set.id);
386                        }
387                        for (IndexReductionEq memberEq : otherSet.eqns) {
388                            set.eqns.add(memberEq);
389                            dsLookup.put(memberEq, set);
390                        }
391                    } else {
392                        set.eqns.add(otherEqn);
393                        dsLookup.put(otherEqn, set);
394                        set.vars.add(otherEqn.getMatching());
395                    }
396                }
397                set.eqns.add(eqn);
398                dsLookup.put(eqn, set);
399                dsSets.add(set);
400                ASTNode.log.debug("  Set added, %d eqns and %d vars", set.eqns.size(), set.vars.size());
401            } else {
402                ASTNode.log.debug("  Set not added, %d eqns and %d vars", set.eqns.size(), set.vars.size());
403            }
404        }
405       
406        for (IndexReductionEq eqn : getEquations()) {
407            if (dsLookup.containsKey(eqn))
408                continue;
409            if (eqn.getMatching() == null)
410                continue; // Possible?
411            Map<IndexReductionVar, Coefficient> coefficients = coefficientsMatrix.get(eqn);
412            if (coefficients == null)
413                continue; // Possible?
414            if (!dynamicSetCandidate(eqn, eqn.getMatching(), coefficients))
415                continue;
416            for (IndexReductionVar var : eqn.getVariables()) {
417                if (eqn.getMatching() == var || var.getMatching() == null)
418                    continue;
419                IndexReductionEq otherEqn = var.getMatching();
420                coefficients = coefficientsMatrix.get(otherEqn);
421                if (!dynamicSetCandidate(eqn, var, coefficients))
422                    continue;
423                DSSet set = dsLookup.get(otherEqn);
424                if (set == null)
425                    continue;
426                set.eqns.add(eqn);
427                set.vars.add(eqn.getMatching());
428                dsLookup.put(eqn, set);
429                break;
430            }
431        }
432       
433        boolean skipDynamicStates = false;
434        for (DSSet set : dsSets) {
435            if (dynamicStateLimit >= 0 && (set.eqns.size() > dynamicStateLimit || set.vars.size() > dynamicStateLimit)) {
436                ASTNode.log.verbose("Too big dynamic state set, %d equations and %d variables!", set.eqns.size(), set.vars.size());
437                ASTNode.log.verbose(set);
438                skipDynamicStates = true;
439            }
440        }
441       
442        if (skipDynamicStates) {
443            ASTNode.log.verbose("Resetting matchings");
444            for (Map.Entry<IndexReductionVar, IndexReductionEq> entry : initialMatching.entrySet()) {
445                IndexReductionVar var = entry.getKey();
446                IndexReductionEq eqn = entry.getValue();
447                var.setMatching(eqn);
448                if (eqn != null)
449                    eqn.setMatching(var);
450            }
451            result.markDSAsFailed();
452            return Collections.emptySet();
453        }
454       
455        Set<IndexReductionVar> vars = new HashSet<IndexReductionVar>();
456        for (DSSet set : dsSets) {
457            if (set.eqns.size() == set.vars.size()) {
458                ASTNode.log.debug("Set %d not added, %d eqns and %d vars", set.id, set.eqns.size(), set.vars.size());
459                continue;
460            } else if (set.eqns.size() > set.vars.size()) {
461                throw new UnsupportedOperationException("Something went wrong during dynamic state selection, dynamic state set " + set.id + " contains " + set.eqns.size() + " equations but only " + set.vars.size() + "variables! Please report this error!");
462            }
463            set.coefficients = new FExp[set.eqns.size()][set.vars.size()];
464            int i = 0;
465            for (IndexReductionEq eqn : set.eqns) {
466                int j = 0;
467                Map<IndexReductionVar, Coefficient> coefficients = coefficientsMatrix.get(eqn);
468                if (coefficients == null)
469                    continue; // Yes this can happen :)
470                for (IndexReductionVar var : set.vars) {
471                    Coefficient coff = coefficients.get(var);
472                    set.coefficients[i][j] = coff == null ? null : coefficients.get(var).exp;
473                    if (set.coefficients[i][j] != null && set.coefficients[i][j].isNoExp())
474                        throw new IndexReductionException("Dynamic state construction failed due to non scalar derivative for variable " + var.getName() + " when differentiating: \n" + eqn.getEquation());
475                    j++;
476                }
477                i++;
478            }
479            ASTNode.log.verbose(set);
480            result.addDSSet(set);
481            vars.addAll(set.vars);
482        }
483        return vars;
484    }
485   
486    public Collection<IndexReductionVar> IndexReductionEq.getVariablesSortedSAP2(final Map<IndexReductionVar, IndexReductionEq> tempAssignmentMap) {
487        java.util.List<IndexReductionVar> res = new ArrayList<IndexReductionVar>(getVariables());
488        Collections.sort(res, new Comparator<IndexReductionVar>() {
489            @Override
490            public int compare(IndexReductionVar a, IndexReductionVar b) {
491                // Get unmatched first
492                int diff = (a.getMatching() == null ? 1 : 0) - (b.getMatching() == null ? 1 : 0);
493                if (diff != 0) {
494                    return -diff;
495                }
496                // Get other variables after the one matched to the equation
497                diff = (a.getMatching() == IndexReductionEq.this ? 1 : 0) - (b.getMatching() == IndexReductionEq.this ? 1 : 0);
498                if (diff != 0) {
499                    return -diff;
500                }
501                // Get non-temporary variables first. Then temporary variables
502                // that are not assigned in its "temporary equation"
503                IndexReductionEq aEq = tempAssignmentMap.get(a);
504                IndexReductionEq bEq = tempAssignmentMap.get(b);
505                diff = (aEq != null ? (aEq.getMatching() != a ? 2 : 1) : 0) - (bEq != null ? (bEq.getMatching() != b ? 2 : 1) : 0);
506                if (diff != 0) {
507                    return -diff;
508                }
509                return a.getName().compareTo(b.getName());
510            }
511        });
512        return res;
513    }
514   
515    public Map<IndexReductionVar, IndexReductionEq> IndexReductionBiPGraph.computeTempAssignmentMap() {
516        Map<IndexReductionVar, IndexReductionEq> res = new HashMap<IndexReductionVar, IndexReductionEq>();
517        for (IndexReductionEq eqn : getEquations()) {
518            FAbstractVariable var = eqn.getEquation().assignedFV();
519            if (var == null || !var.isTemporary()) {
520                continue;
521            }
522            IndexReductionVar bipVar = getVariable(var.name());
523            if (bipVar == null) {
524                continue;
525            }
526            res.put(bipVar, eqn);
527        }
528        return res;
529    }
530   
531    public boolean IndexReductionBiPGraph.dynamicSetCandidate(IndexReductionEq eqn, IndexReductionVar var,
532            Map<IndexReductionVar, Coefficient> coefficients) {
533        return var.dynamicSetCandidate(coefficients.get(var), computeIncidenceStateSelect(eqn, var));
534    }
535
536    public boolean IndexReductionVar.dynamicSetCandidate(IndexReductionBiPGraph.Coefficient coefficient, FVariable.StateSelect stateSelect) {
537        if (coefficient == null)
538            return false;
539        if (coefficient.state != IndexReductionBiPGraph.COEFFICIENT_STATE.CONTINUOUS)
540            return false;
541        return dynamicSetCandidate(stateSelect);
542    }
543    public boolean IndexReductionVar.dynamicSetCandidate(FVariable.StateSelect stateSelect) {
544        return stateSelect != FVariable.StateSelect.NEVER && stateSelect != FVariable.StateSelect.ALWAYS;
545    }
546
547    public FVariable.StateSelect IndexReductionBiPGraph.computeIncidenceStateSelect(IndexReductionEq eq, IndexReductionVar var) {
548        if (var.getVariable().stateSelection() == FVariable.StateSelect.ALWAYS) {
549            return FVariable.StateSelect.ALWAYS;
550        }
551        for (FAccessExp exp : eq.getEquation().findFAccessExpsInTree()) {
552            if (getVariable(exp.name()) == var && !exp.getOriginalVariable().isEmpty()) {
553                return exp.myOriginalFV().stateSelection();
554            }
555        }
556        return var.getVariable().stateSelection();
557    }
558   
559
560    public Object IndexReductionBiPGraph.printCoefficientsObj(final Map<IndexReductionEq, Map<IndexReductionVar, Coefficient>> coefficientsMatrix, final boolean printExpressions) {
561        return new Object() {
562            public String toString() {
563                StringBuilder sb = new StringBuilder();
564                for (IndexReductionVar var : getVariables()) {
565                    sb.append('\t');
566                    sb.append(var);
567                }
568                sb.append('\n');
569                for (IndexReductionEq eqn : getEquations()) {
570                    sb.append(eqn);
571                    Map<IndexReductionVar, Coefficient> coefficients = coefficientsMatrix.get(eqn);
572                    if (coefficients == null)
573                        coefficients = Collections.emptyMap();
574                    for (IndexReductionVar var : getVariables()) {
575                        sb.append('\t');
576                        Coefficient coff = coefficients.get(var);
577                        if (coff == null)
578                            continue;
579                        if (printExpressions) {
580                            sb.append(coff.exp);
581                        } else {
582                            switch (coff.state) {
583                            case CONTINUOUS:
584                                sb.append('+');
585                                break;
586                            case EXCEPTION:
587                                sb.append('X');
588                                break;
589                            case SPLIT:
590                                sb.append('S');
591                                break;
592                            default:
593                                sb.append('*');
594                            }
595                        }
596                    }
597                    sb.append('\n');
598                }
599                return sb.toString();
600            }
601        };
602    }
603
604    private Collection<IndexReductionBiPGraph.DSSet> IndexReductionResult.dsSets = new ArrayList<IndexReductionBiPGraph.DSSet>();
605
606    public void IndexReductionResult.addDSSet(IndexReductionBiPGraph.DSSet set) {
607        dsSets.add(set);
608    }
609
610    public Collection<IndexReductionBiPGraph.DSSet> IndexReductionResult.getDSSets() {
611        return dsSets;
612    }
613
614    public void IndexReductionResult.markDSAsFailed() {
615        dsSets = null;
616    }
617
618    public boolean IndexReductionResult.hasDSFailed() {
619        return dsSets == null;
620    }
621
622    public class IndexReductionBiPGraph {
623       
624        public class SAP1 extends StandardAugmentingPath {
625            private final Set<IndexReductionEq> dsEqns;
626            private final Map<IndexReductionEq, Map<IndexReductionVar, Coefficient>> coefficientsMatrix;
627           
628            public SAP1(Set<IndexReductionEq> dsEqns, Map<IndexReductionEq, Map<IndexReductionVar, Coefficient>> coefficientsMatrix) {
629                this.dsEqns = dsEqns;
630                this.coefficientsMatrix = coefficientsMatrix;
631            }
632
633            @Override
634            protected Iterable<IndexReductionVar> visitVariables(IndexReductionEq eqn) {
635                if (dsEqns.contains(eqn))
636                    return Collections.emptyList();
637                else
638                    return super.visitVariables(eqn);
639            }
640
641            @Override
642            protected boolean shouldVisit(IndexReductionEq eqn, IndexReductionVar var) {
643                if (!super.shouldVisit(eqn, var))
644                    return false;
645                if (var.numDifferentiations() < eqn.numDifferentiations()) {
646                    return false;
647                }
648                Map<IndexReductionVar, Coefficient> coefficients =  coefficientsMatrix.get(eqn);
649                if (coefficients != null) {
650                    Coefficient coff = coefficients.get(var);
651                    if (coff != null && coff.state == COEFFICIENT_STATE.CONTINUOUS)
652                        return false;
653                }
654                return var.dynamicSetCandidate(computeIncidenceStateSelect(eqn, var));
655            }
656            @Override
657            protected void match(IndexReductionEq eqn, IndexReductionVar var) {
658                IndexReductionVar previous = eqn.getMatching();
659                super.match(eqn, var);
660                ASTNode.log.debug("      Rematch %s to %s (previous %s)", eqn, var, previous);
661            }
662        }
663
664        public class SAP2 extends AugmentingPathAlgorithm<Collection<IndexReductionEq>> {
665            private final Set<IndexReductionEq> dsEqns;
666            private final Map<IndexReductionEq, Map<IndexReductionVar, Coefficient>> coefficientsMatrix;
667            private final Queue<IndexReductionEq> worklist;
668           
669            public SAP2(Set<IndexReductionEq> dsEqns, Map<IndexReductionEq, Map<IndexReductionVar, Coefficient>> coefficientsMatrix, Queue<IndexReductionEq> worklist) {
670                super(Collections.unmodifiableCollection(new ArrayList<IndexReductionEq>()));
671                this.dsEqns = dsEqns;
672                this.coefficientsMatrix = coefficientsMatrix;
673                this.worklist = worklist;
674            }
675           
676            @Override
677            protected Collection<IndexReductionEq> startValue(IndexReductionEq eqn) {
678                if (dsEqns.contains(eqn))
679                    return Collections.singletonList(eqn);
680                else
681                    return Collections.emptyList();
682            }
683
684            @Override
685            protected Iterable<IndexReductionVar> visitVariables(IndexReductionEq eqn) {
686                if (dsEqns.contains(eqn))
687                    return Collections.emptyList();
688                else
689                    return super.visitVariables(eqn);
690            }
691
692            @Override
693            protected Collection<IndexReductionEq> mergeSubRes(Collection<IndexReductionEq> res, Collection<IndexReductionEq> subRes, IndexReductionEq eqn) {
694                if (subRes.size() > 0) {
695                    if (res.isEmpty())
696                        res = new ArrayList<IndexReductionEq>();
697                    res.addAll(subRes);
698                    res.add(eqn);
699                }
700                return res;
701            }
702   
703            @Override
704            protected void match(IndexReductionEq eqn, IndexReductionVar var) {
705                IndexReductionVar previous = eqn.getMatching();
706                super.match(eqn, var);
707                ASTNode.log.debug("      Rematch %s to %s (previous %s)", eqn, var, previous);
708                Map<IndexReductionVar, Coefficient> coefficients = coefficientsMatrix.get(eqn);
709                if (coefficients == null)
710                    return;
711                Coefficient coff = coefficients.get(var);
712                if (coff != null && coff.state == COEFFICIENT_STATE.CONTINUOUS) {
713                    ASTNode.log.debug("      Adding %s to worklist", eqn);
714                    worklist.add(eqn);
715                }
716            }
717           
718            @Override
719            protected boolean shouldVisit(IndexReductionEq eqn, IndexReductionVar var) {
720                if (!super.shouldVisit(eqn, var)) {
721                    return false;
722                }
723                if (var.numDifferentiations() < eqn.numDifferentiations()) {
724                    return false;
725                }
726                return var.dynamicSetCandidate(computeIncidenceStateSelect(eqn, var));
727            }
728        }
729    }
730   
731    public boolean IndexReductionEq.isTempAssignmentFor(IndexReductionVar var) {
732        if (!var.getVariable().isTemporary()) {
733            return false;
734        }
735        return getEquation().assignedFV() == var.getVariable();
736    }
737   
738    public boolean SCCBlock.containsDynamicStates() {
739        for (E eqn : this)
740            if (!eqn.isMeta() && eqn.getMatching().getVariable().isFDynamicAlgebraicVariable())
741                return true;
742        return false;
743    }
744   
745    public class EquationBlockFactory {
746       
747        private static <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> DynamicStateBlock computeDynamicStateBlock(SCCBlock<E, V> component, BlockProducer producer, StepUtil stepUtil) {
748            final Map<DynamicStateSet, FDynamicAlgebraicVariable[]> setVarMap = new LinkedHashMap<DynamicStateSet, FDynamicAlgebraicVariable[]>();
749            Collection<V> otherVars = new ArrayList<V>();
750            for (E eqn : component.getMembers()) {
751                if (eqn.isMeta()) {
752                    continue;
753                }
754                FVariable fVar = eqn.getMatching().getVariable();
755                if (!fVar.isFDynamicAlgebraicVariable()) {
756                    otherVars.add(eqn.getMatching());
757                    continue;
758                }
759                FDynamicAlgebraicVariable var = fVar.asFDynamicAlgebraicVariable();
760                DynamicStateSet set = var.getSet();
761                if (var.getNumber() - 1 >= set.numAlgebraics() || var.getNumber() - 1 < 0)
762                    throw new BLTException(var.name() + " has illegal dynamic state variable number, set size is " + set.numAlgebraics());
763                FDynamicAlgebraicVariable[] vars = setVarMap.get(set);
764                if (vars == null) {
765                    vars = new FDynamicAlgebraicVariable[set.numAlgebraics()];
766                    setVarMap.put(set, vars);
767                }
768                if (vars[var.getNumber() - 1] != null)
769                    throw new BLTException("There are two instances of " + var.name() + " in the same BLT block!");
770                vars[var.getNumber() - 1] = var;
771            }
772            if (setVarMap.isEmpty())
773                throw new BLTException("No dynamic state variables were found in the BLT block");
774            FVariable[][][] setCombinations = new FVariable[setVarMap.size()][][];
775            int setCounter = 0;
776            int totalNumAlgebraics = 0;
777            int totalNumCombinations = 1;
778            final Collection<FVariable> allDynamicStates = new ArrayList<FVariable>();
779            for (Map.Entry<DynamicStateSet, FDynamicAlgebraicVariable[]> entry : setVarMap.entrySet()) {
780                boolean allSet = true;
781                DynamicStateSet set = entry.getKey();
782                FDynamicAlgebraicVariable[] DSVars = entry.getValue();
783                for (int i = 1; i <= DSVars.length; i++) {
784                    if (DSVars[i - 1] == null) {
785                        allSet = false;
786                    }
787                }
788                if (!allSet) {
789                    StringBuilder sb = new StringBuilder();
790                    sb.append("Not all dynamic state variables resides in the same block, index ");
791                    boolean first = true;
792                    for (int i = 1; i <= DSVars.length; i++) {
793                        if (DSVars[i - 1] != null)
794                            continue;
795                        if (!first)
796                            sb.append(", ");
797                        first = false;
798                        sb.append(i);
799                    }
800                    sb.append(" are missing. Set:\n");
801                    sb.append(set);
802                    throw new BLTException(sb.toString());
803                }
804                setCombinations[setCounter] = set.algebraicCombinations();
805                allDynamicStates.addAll(set.fVarsColl());
806                totalNumAlgebraics += set.numAlgebraics();
807                totalNumCombinations *= set.numCombinations();
808                setCounter++;
809            }
810            if (totalNumCombinations > 42)
811                throw new BLTException("Ouch! There are more than 42 combinations for the dynamic states, there were " + totalNumCombinations + " combinations!");
812            FVariable[][] combinations = combineDSCombinations(setCombinations, totalNumAlgebraics);
813            DynamicStateBLT[] blts = new DynamicStateBLT[combinations.length];
814            calculateBlockBLTs(blts, component, producer, stepUtil, combinations, otherVars,
815                    new BLTProducer<DynamicStateBLT>() {
816                @Override
817                public DynamicStateBLT create(FVariable[] combination) {
818                    Set<FVariable> algebraics = new LinkedHashSet<FVariable>(Arrays.asList(combination));
819                    Collection<FVariable> states = new ArrayList<FVariable>();
820                    for (FVariable var : allDynamicStates) {
821                        if (!algebraics.contains(var)) {
822                            states.add(var);
823                        }
824                    }
825                    return new DynamicStateBLT(setVarMap.keySet(), states, algebraics);
826                }
827            });
828            return new DynamicStateBlock(producer, component.computeBlockDependency(), blts, setVarMap.keySet());
829        }
830       
831        interface BLTProducer<B extends BLT> {
832            B create(FVariable[] combination);
833        }
834       
835        public static <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, B extends BLT> void calculateBlockBLTs(B[] blts, SCCBlock<E, V> component, 
836                BlockProducer producer, StepUtil stepUtil, 
837                FVariable[][] combinations, Collection<V> otherVars, BLTProducer<B> bltProducer) {
838            for (int i = 0; i < combinations.length; i++) {
839                FVariable[] combination = combinations[i];
840                StringBuilder sb = new StringBuilder();
841                for (int j = 0; j < combination.length; j++) {
842                    sb.append(combination[j].name() + " ");
843                }
844                ASTNode.log.debug("Generating BLT for: %s", sb);
845                BiPGraph graph = new BiPGraph(component.getMembers(), otherVars);
846                for (FVariable var : combination)
847                    graph.addVariable(var);
848                for (Eq eqn : graph.getEquations()) {
849                    Set<FVariable> vars = eqn.getEquation().referencedFVariables();
850                    for (FVariable var : combination)
851                        if (vars.contains(var))
852                            graph.addEdge(eqn, graph.getVariable(var.name()));
853                }
854                ASTNode.log.debug(graph);
855                graph.maximumMatching(true);
856                B blt = bltProducer.create(combination);
857                if (graph.isComplete()) {
858                    blt = graph.computeBLT(stepUtil, producer, blt, false);
859                } else {
860                    ASTNode.log.verbose("  This combination does not have a valid solution!");
861                    ASTNode.log.debug(graph.printMatchingObj());
862                }
863                ASTNode.log.debug(blt);
864                blts[i] = blt;
865            }
866        }
867    }
868   
869
870}
Note: See TracBrowser for help on using the repository browser.