source: trunk/Compiler/ModelicaMiddleEnd/src/jastadd/structural/DynamicStates.jrag @ 13357

Last change on this file since 13357 was 13357, checked in by Jonathan Kämpe, 4 months ago

#5766 Merging refactoring from branch

File size: 39.6 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            private static Enumerator e = new Enumerator();
266            public final Set<IndexReductionEq> eqns = new LinkedHashSet<IndexReductionEq>();
267            public final Set<IndexReductionVar> vars = new LinkedHashSet<IndexReductionVar>();
268            public final int id = e.next();
269            public FExp[][] coefficients;
270           
271            public String toString() {
272                StringBuilder sb = new StringBuilder();
273                sb.append(String.format("Set %d, %d equations and %d variables:\n", id, eqns.size(), vars.size()));
274                sb.append("  Equations:\n");
275                for (IndexReductionEq eqn : eqns)
276                    sb.append("    " + eqn + "\n");
277                sb.append("  Variables:\n");
278                for (IndexReductionVar var : vars)
279                    sb.append("    " + var + "\n");
280                return sb.toString();
281            }
282        }
283       
284    }
285
286    public Set<IndexReductionVar> IndexReductionBiPGraph.computeDynamicStateSets(int dynamicStateLimit, 
287            Map<IndexReductionEq, Map<IndexReductionVar, Coefficient>> coefficientsMatrix, IndexReductionResult result) {
288        if (result.hasDSFailed())
289            return Collections.emptySet();
290        Map<IndexReductionVar, IndexReductionEq> initialMatching = new HashMap<IndexReductionVar, IndexReductionEq>();
291        for (IndexReductionVar var : getVariables())
292            initialMatching.put(var, var.getMatching());
293       
294        Map<IndexReductionVar, IndexReductionEq> tempAssignmentMap = computeTempAssignmentMap();
295       
296        ASTNode.log.verbose(printCoefficientsObj(coefficientsMatrix, false));
297        ASTNode.log.verbose(printCoefficientsObj(coefficientsMatrix, true));
298        Set<DSSet> dsSets = new LinkedHashSet<DSSet>();
299        Map<IndexReductionEq, DSSet> dsLookup = new HashMap<IndexReductionEq, DSSet>();
300        Queue<IndexReductionEq> worklist = new ArrayDeque<IndexReductionEq>();
301        SAP1 sap1 = new SAP1(dsLookup.keySet(), coefficientsMatrix);
302        SAP2 sap2 = new SAP2(dsLookup.keySet(), coefficientsMatrix, worklist);
303        for (IndexReductionEq eqn : getEquations()) {
304            Map<IndexReductionVar, Coefficient> coefficients = coefficientsMatrix.get(eqn);
305            if (coefficients == null)
306                continue;
307            Coefficient coff = coefficients.get(eqn.getMatching());
308            if (coff != null && coff.state == COEFFICIENT_STATE.CONTINUOUS)
309                worklist.add(eqn);
310        }
311        while (!worklist.isEmpty()) {
312            IndexReductionEq eqn = worklist.poll();
313            ASTNode.log.debug("Looking for DS in %s", eqn);
314            Map<IndexReductionVar, Coefficient> coefficients = coefficientsMatrix.get(eqn);
315            if (coefficients == null)
316                continue;
317            if (!dynamicSetCandidate(eqn, eqn.getMatching(), coefficients))
318                continue;
319            lightReset();
320            ASTNode.log.debug("  SAP1");
321            if (sap1.augmentingPath(eqn)) {
322                continue;
323            }
324            DSSet set = dsLookup.get(eqn);
325            if (set == null)
326                set = new DSSet();
327            Collection<IndexReductionEq> otherEqns = new ArrayList<IndexReductionEq>();
328            ASTNode.log.debug("    Path not found, set %d", set.id);
329            for (IndexReductionVar var : eqn.getVariablesSortedSAP2(tempAssignmentMap)) {
330                if (!dynamicSetCandidate(eqn, var, coefficients))
331                    continue;
332                ASTNode.log.debug("  Checking ncc variable %s", var);
333                if (var.getMatching() == eqn) {
334                    set.vars.add(var);
335                    ASTNode.log.debug("    adding %s to set %d", var, set.id);
336                } else if (var.getMatching() == null) {
337                    set.vars.add(var);
338                    var.setMatching(eqn);
339                    ASTNode.log.debug("    adding %s to set %d", var, set.id);
340                } else {
341                    IndexReductionEq tmpAssignEqn = tempAssignmentMap.get(var);
342                    if (tmpAssignEqn != null) {
343                        if (tmpAssignEqn.getMatching() != var && dsLookup.get(tmpAssignEqn) == null) {
344                            set.vars.add(tmpAssignEqn.getMatching());
345                            set.eqns.add(tmpAssignEqn);
346                            continue;
347                        }
348                    }
349                    lightReset();
350                    DSSet otherSet = dsLookup.get(var.getMatching());
351                    Collection<IndexReductionVar> noVisit = new ArrayList<IndexReductionVar>();
352                    if (otherSet != null)
353                        noVisit.addAll(otherSet.vars);
354                    noVisit.addAll(set.vars);
355                    noVisit.add(eqn.getMatching());
356                    noVisit.add(var);
357                    ASTNode.log.debug("    SAP2 %s", var.getMatching());
358                    Collection<IndexReductionEq> res = sap2.augmentingPath(var.getMatching(), noVisit);
359                    if (res == sap2.trueValue()) {
360                        ASTNode.log.debug("      Path found");
361                        set.vars.add(var);
362                        var.setMatching(eqn);
363                        ASTNode.log.debug("      adding %s to set %d", var, set.id);
364                    } else {
365                        ASTNode.log.debug("      Path not found");
366                        for (IndexReductionEq resEqn : res)
367                            ASTNode.log.debug("      Adding %s to set.eqns", resEqn);
368                        otherEqns.addAll(res);
369                    }
370                }
371            }
372            if (set.vars.size() >= 2 || set.eqns.size() > 0 || otherEqns.size() > 0) {
373                for (IndexReductionEq otherEqn : otherEqns) {
374                    DSSet otherSet = dsLookup.remove(otherEqn);
375                    if (otherSet != null) {
376                        ASTNode.log.debug("  Merging with set %d from %s", otherSet.id, otherEqn);
377                        dsSets.remove(otherSet);
378                        for (IndexReductionVar memberVar : otherSet.vars) {
379                            set.vars.add(memberVar);
380                            ASTNode.log.debug("    adding %s to set %d", memberVar, set.id);
381                        }
382                        for (IndexReductionEq memberEq : otherSet.eqns) {
383                            set.eqns.add(memberEq);
384                            dsLookup.put(memberEq, set);
385                        }
386                    } else {
387                        set.eqns.add(otherEqn);
388                        dsLookup.put(otherEqn, set);
389                        set.vars.add(otherEqn.getMatching());
390                    }
391                }
392                set.eqns.add(eqn);
393                dsLookup.put(eqn, set);
394                dsSets.add(set);
395                ASTNode.log.debug("  Set added, %d eqns and %d vars", set.eqns.size(), set.vars.size());
396            } else {
397                ASTNode.log.debug("  Set not added, %d eqns and %d vars", set.eqns.size(), set.vars.size());
398            }
399        }
400       
401        for (IndexReductionEq eqn : getEquations()) {
402            if (dsLookup.containsKey(eqn))
403                continue;
404            if (eqn.getMatching() == null)
405                continue; // Possible?
406            Map<IndexReductionVar, Coefficient> coefficients = coefficientsMatrix.get(eqn);
407            if (coefficients == null)
408                continue; // Possible?
409            if (!dynamicSetCandidate(eqn, eqn.getMatching(), coefficients))
410                continue;
411            for (IndexReductionVar var : eqn.getVariables()) {
412                if (eqn.getMatching() == var || var.getMatching() == null)
413                    continue;
414                IndexReductionEq otherEqn = var.getMatching();
415                coefficients = coefficientsMatrix.get(otherEqn);
416                if (!dynamicSetCandidate(eqn, var, coefficients))
417                    continue;
418                DSSet set = dsLookup.get(otherEqn);
419                if (set == null)
420                    continue;
421                set.eqns.add(eqn);
422                set.vars.add(eqn.getMatching());
423                dsLookup.put(eqn, set);
424                break;
425            }
426        }
427       
428        boolean skipDynamicStates = false;
429        for (DSSet set : dsSets) {
430            if (dynamicStateLimit >= 0 && (set.eqns.size() > dynamicStateLimit || set.vars.size() > dynamicStateLimit)) {
431                ASTNode.log.verbose("Too big dynamic state set, %d equations and %d variables!", set.eqns.size(), set.vars.size());
432                ASTNode.log.verbose(set);
433                skipDynamicStates = true;
434            }
435        }
436       
437        if (skipDynamicStates) {
438            ASTNode.log.verbose("Resetting matchings");
439            for (Map.Entry<IndexReductionVar, IndexReductionEq> entry : initialMatching.entrySet()) {
440                IndexReductionVar var = entry.getKey();
441                IndexReductionEq eqn = entry.getValue();
442                var.setMatching(eqn);
443                if (eqn != null)
444                    eqn.setMatching(var);
445            }
446            result.markDSAsFailed();
447            return Collections.emptySet();
448        }
449       
450        Set<IndexReductionVar> vars = new HashSet<IndexReductionVar>();
451        for (DSSet set : dsSets) {
452            if (set.eqns.size() == set.vars.size()) {
453                ASTNode.log.debug("Set %d not added, %d eqns and %d vars", set.id, set.eqns.size(), set.vars.size());
454                continue;
455            } else if (set.eqns.size() > set.vars.size()) {
456                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!");
457            }
458            set.coefficients = new FExp[set.eqns.size()][set.vars.size()];
459            int i = 0;
460            for (IndexReductionEq eqn : set.eqns) {
461                int j = 0;
462                Map<IndexReductionVar, Coefficient> coefficients = coefficientsMatrix.get(eqn);
463                if (coefficients == null)
464                    continue; // Yes this can happen :)
465                for (IndexReductionVar var : set.vars) {
466                    Coefficient coff = coefficients.get(var);
467                    set.coefficients[i][j] = coff == null ? null : coefficients.get(var).exp;
468                    if (set.coefficients[i][j] != null && set.coefficients[i][j].isNoExp())
469                        throw new IndexReductionException("Dynamic state construction failed due to non scalar derivative for variable " + var.getName() + " when differentiating: \n" + eqn.getEquation());
470                    j++;
471                }
472                i++;
473            }
474            ASTNode.log.verbose(set);
475            result.addDSSet(set);
476            vars.addAll(set.vars);
477        }
478        return vars;
479    }
480   
481    public Collection<IndexReductionVar> IndexReductionEq.getVariablesSortedSAP2(final Map<IndexReductionVar, IndexReductionEq> tempAssignmentMap) {
482        java.util.List<IndexReductionVar> res = new ArrayList<IndexReductionVar>(getVariables());
483        Collections.sort(res, new Comparator<IndexReductionVar>() {
484            @Override
485            public int compare(IndexReductionVar a, IndexReductionVar b) {
486                // Get unmatched first
487                int diff = (a.getMatching() == null ? 1 : 0) - (b.getMatching() == null ? 1 : 0);
488                if (diff != 0) {
489                    return -diff;
490                }
491                // Get other variables after the one matched to the equation
492                diff = (a.getMatching() == IndexReductionEq.this ? 1 : 0) - (b.getMatching() == IndexReductionEq.this ? 1 : 0);
493                if (diff != 0) {
494                    return -diff;
495                }
496                // Get non-temporary variables first. Then temporary variables
497                // that are not assigned in its "temporary equation"
498                IndexReductionEq aEq = tempAssignmentMap.get(a);
499                IndexReductionEq bEq = tempAssignmentMap.get(b);
500                diff = (aEq != null ? (aEq.getMatching() != a ? 2 : 1) : 0) - (bEq != null ? (bEq.getMatching() != b ? 2 : 1) : 0);
501                if (diff != 0) {
502                    return -diff;
503                }
504                return a.getName().compareTo(b.getName());
505            }
506        });
507        return res;
508    }
509   
510    public Map<IndexReductionVar, IndexReductionEq> IndexReductionBiPGraph.computeTempAssignmentMap() {
511        Map<IndexReductionVar, IndexReductionEq> res = new HashMap<IndexReductionVar, IndexReductionEq>();
512        for (IndexReductionEq eqn : getEquations()) {
513            FAbstractVariable var = eqn.getEquation().assignedFV();
514            if (var == null || !var.isTemporary()) {
515                continue;
516            }
517            IndexReductionVar bipVar = getVariable(var.name());
518            if (bipVar == null) {
519                continue;
520            }
521            res.put(bipVar, eqn);
522        }
523        return res;
524    }
525   
526    public boolean IndexReductionBiPGraph.dynamicSetCandidate(IndexReductionEq eqn, IndexReductionVar var,
527            Map<IndexReductionVar, Coefficient> coefficients) {
528        return var.dynamicSetCandidate(coefficients.get(var), computeIncidenceStateSelect(eqn, var));
529    }
530
531    public boolean IndexReductionVar.dynamicSetCandidate(IndexReductionBiPGraph.Coefficient coefficient, FVariable.StateSelect stateSelect) {
532        if (coefficient == null)
533            return false;
534        if (coefficient.state != IndexReductionBiPGraph.COEFFICIENT_STATE.CONTINUOUS)
535            return false;
536        return dynamicSetCandidate(stateSelect);
537    }
538    public boolean IndexReductionVar.dynamicSetCandidate(FVariable.StateSelect stateSelect) {
539        return stateSelect != FVariable.StateSelect.NEVER && stateSelect != FVariable.StateSelect.ALWAYS;
540    }
541
542    public FVariable.StateSelect IndexReductionBiPGraph.computeIncidenceStateSelect(IndexReductionEq eq, IndexReductionVar var) {
543        if (var.getVariable().stateSelection() == FVariable.StateSelect.ALWAYS) {
544            return FVariable.StateSelect.ALWAYS;
545        }
546        for (FAccessExp exp : eq.getEquation().findFAccessExpsInTree()) {
547            if (getVariable(exp.name()) == var && !exp.getOriginalVariable().isEmpty()) {
548                return exp.myOriginalFV().stateSelection();
549            }
550        }
551        return var.getVariable().stateSelection();
552    }
553   
554
555    public Object IndexReductionBiPGraph.printCoefficientsObj(final Map<IndexReductionEq, Map<IndexReductionVar, Coefficient>> coefficientsMatrix, final boolean printExpressions) {
556        return new Object() {
557            public String toString() {
558                StringBuilder sb = new StringBuilder();
559                for (IndexReductionVar var : getVariables()) {
560                    sb.append('\t');
561                    sb.append(var);
562                }
563                sb.append('\n');
564                for (IndexReductionEq eqn : getEquations()) {
565                    sb.append(eqn);
566                    Map<IndexReductionVar, Coefficient> coefficients = coefficientsMatrix.get(eqn);
567                    if (coefficients == null)
568                        coefficients = Collections.emptyMap();
569                    for (IndexReductionVar var : getVariables()) {
570                        sb.append('\t');
571                        Coefficient coff = coefficients.get(var);
572                        if (coff == null)
573                            continue;
574                        if (printExpressions) {
575                            sb.append(coff.exp);
576                        } else {
577                            switch (coff.state) {
578                            case CONTINUOUS:
579                                sb.append('+');
580                                break;
581                            case EXCEPTION:
582                                sb.append('X');
583                                break;
584                            case SPLIT:
585                                sb.append('S');
586                                break;
587                            default:
588                                sb.append('*');
589                            }
590                        }
591                    }
592                    sb.append('\n');
593                }
594                return sb.toString();
595            }
596        };
597    }
598
599    private Collection<IndexReductionBiPGraph.DSSet> IndexReductionResult.dsSets = new ArrayList<IndexReductionBiPGraph.DSSet>();
600
601    public void IndexReductionResult.addDSSet(IndexReductionBiPGraph.DSSet set) {
602        dsSets.add(set);
603    }
604
605    public Collection<IndexReductionBiPGraph.DSSet> IndexReductionResult.getDSSets() {
606        return dsSets;
607    }
608
609    public void IndexReductionResult.markDSAsFailed() {
610        dsSets = null;
611    }
612
613    public boolean IndexReductionResult.hasDSFailed() {
614        return dsSets == null;
615    }
616
617    public class IndexReductionBiPGraph {
618       
619        public class SAP1 extends StandardAugmentingPath {
620            private final Set<IndexReductionEq> dsEqns;
621            private final Map<IndexReductionEq, Map<IndexReductionVar, Coefficient>> coefficientsMatrix;
622           
623            public SAP1(Set<IndexReductionEq> dsEqns, Map<IndexReductionEq, Map<IndexReductionVar, Coefficient>> coefficientsMatrix) {
624                this.dsEqns = dsEqns;
625                this.coefficientsMatrix = coefficientsMatrix;
626            }
627
628            @Override
629            protected Iterable<IndexReductionVar> visitVariables(IndexReductionEq eqn) {
630                if (dsEqns.contains(eqn))
631                    return Collections.emptyList();
632                else
633                    return super.visitVariables(eqn);
634            }
635
636            @Override
637            protected boolean shouldVisit(IndexReductionEq eqn, IndexReductionVar var) {
638                if (!super.shouldVisit(eqn, var))
639                    return false;
640                if (var.numDifferentiations() < eqn.numDifferentiations()) {
641                    return false;
642                }
643                Map<IndexReductionVar, Coefficient> coefficients =  coefficientsMatrix.get(eqn);
644                if (coefficients != null) {
645                    Coefficient coff = coefficients.get(var);
646                    if (coff != null && coff.state == COEFFICIENT_STATE.CONTINUOUS)
647                        return false;
648                }
649                return var.dynamicSetCandidate(computeIncidenceStateSelect(eqn, var));
650            }
651            @Override
652            protected void match(IndexReductionEq eqn, IndexReductionVar var) {
653                IndexReductionVar previous = eqn.getMatching();
654                super.match(eqn, var);
655                ASTNode.log.debug("      Rematch %s to %s (previous %s)", eqn, var, previous);
656            }
657        }
658
659        public class SAP2 extends AugmentingPathAlgorithm<Collection<IndexReductionEq>> {
660            private final Set<IndexReductionEq> dsEqns;
661            private final Map<IndexReductionEq, Map<IndexReductionVar, Coefficient>> coefficientsMatrix;
662            private final Queue<IndexReductionEq> worklist;
663           
664            public SAP2(Set<IndexReductionEq> dsEqns, Map<IndexReductionEq, Map<IndexReductionVar, Coefficient>> coefficientsMatrix, Queue<IndexReductionEq> worklist) {
665                super(Collections.unmodifiableCollection(new ArrayList<IndexReductionEq>()));
666                this.dsEqns = dsEqns;
667                this.coefficientsMatrix = coefficientsMatrix;
668                this.worklist = worklist;
669            }
670           
671            @Override
672            protected Collection<IndexReductionEq> startValue(IndexReductionEq eqn) {
673                if (dsEqns.contains(eqn))
674                    return Collections.singletonList(eqn);
675                else
676                    return Collections.emptyList();
677            }
678
679            @Override
680            protected Iterable<IndexReductionVar> visitVariables(IndexReductionEq eqn) {
681                if (dsEqns.contains(eqn))
682                    return Collections.emptyList();
683                else
684                    return super.visitVariables(eqn);
685            }
686
687            @Override
688            protected Collection<IndexReductionEq> mergeSubRes(Collection<IndexReductionEq> res, Collection<IndexReductionEq> subRes, IndexReductionEq eqn) {
689                if (subRes.size() > 0) {
690                    if (res.isEmpty())
691                        res = new ArrayList<IndexReductionEq>();
692                    res.addAll(subRes);
693                    res.add(eqn);
694                }
695                return res;
696            }
697   
698            @Override
699            protected void match(IndexReductionEq eqn, IndexReductionVar var) {
700                IndexReductionVar previous = eqn.getMatching();
701                super.match(eqn, var);
702                ASTNode.log.debug("      Rematch %s to %s (previous %s)", eqn, var, previous);
703                Map<IndexReductionVar, Coefficient> coefficients = coefficientsMatrix.get(eqn);
704                if (coefficients == null)
705                    return;
706                Coefficient coff = coefficients.get(var);
707                if (coff != null && coff.state == COEFFICIENT_STATE.CONTINUOUS) {
708                    ASTNode.log.debug("      Adding %s to worklist", eqn);
709                    worklist.add(eqn);
710                }
711            }
712           
713            @Override
714            protected boolean shouldVisit(IndexReductionEq eqn, IndexReductionVar var) {
715                if (!super.shouldVisit(eqn, var)) {
716                    return false;
717                }
718                if (var.numDifferentiations() < eqn.numDifferentiations()) {
719                    return false;
720                }
721                return var.dynamicSetCandidate(computeIncidenceStateSelect(eqn, var));
722            }
723        }
724    }
725   
726    public boolean IndexReductionEq.isTempAssignmentFor(IndexReductionVar var) {
727        if (!var.getVariable().isTemporary()) {
728            return false;
729        }
730        return getEquation().assignedFV() == var.getVariable();
731    }
732   
733    public boolean SCCBlock.containsDynamicStates() {
734        for (E eqn : this)
735            if (!eqn.isMeta() && eqn.getMatching().getVariable().isFDynamicAlgebraicVariable())
736                return true;
737        return false;
738    }
739   
740    public class EquationBlockFactory {
741       
742        private static <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> DynamicStateBlock computeDynamicStateBlock(SCCBlock<E, V> component, BlockProducer producer, StepUtil stepUtil) {
743            final Map<DynamicStateSet, FDynamicAlgebraicVariable[]> setVarMap = new LinkedHashMap<DynamicStateSet, FDynamicAlgebraicVariable[]>();
744            Collection<V> otherVars = new ArrayList<V>();
745            for (E eqn : component.getMembers()) {
746                if (eqn.isMeta()) {
747                    continue;
748                }
749                FVariable fVar = eqn.getMatching().getVariable();
750                if (!fVar.isFDynamicAlgebraicVariable()) {
751                    otherVars.add(eqn.getMatching());
752                    continue;
753                }
754                FDynamicAlgebraicVariable var = fVar.asFDynamicAlgebraicVariable();
755                DynamicStateSet set = var.getSet();
756                if (var.getNumber() - 1 >= set.numAlgebraics() || var.getNumber() - 1 < 0)
757                    throw new BLTException(var.name() + " has illegal dynamic state variable number, set size is " + set.numAlgebraics());
758                FDynamicAlgebraicVariable[] vars = setVarMap.get(set);
759                if (vars == null) {
760                    vars = new FDynamicAlgebraicVariable[set.numAlgebraics()];
761                    setVarMap.put(set, vars);
762                }
763                if (vars[var.getNumber() - 1] != null)
764                    throw new BLTException("There are two instances of " + var.name() + " in the same BLT block!");
765                vars[var.getNumber() - 1] = var;
766            }
767            if (setVarMap.isEmpty())
768                throw new BLTException("No dynamic state variables were found in the BLT block");
769            FVariable[][][] setCombinations = new FVariable[setVarMap.size()][][];
770            int setCounter = 0;
771            int totalNumAlgebraics = 0;
772            int totalNumCombinations = 1;
773            final Collection<FVariable> allDynamicStates = new ArrayList<FVariable>();
774            for (Map.Entry<DynamicStateSet, FDynamicAlgebraicVariable[]> entry : setVarMap.entrySet()) {
775                boolean allSet = true;
776                DynamicStateSet set = entry.getKey();
777                FDynamicAlgebraicVariable[] DSVars = entry.getValue();
778                for (int i = 1; i <= DSVars.length; i++) {
779                    if (DSVars[i - 1] == null) {
780                        allSet = false;
781                    }
782                }
783                if (!allSet) {
784                    StringBuilder sb = new StringBuilder();
785                    sb.append("Not all dynamic state variables resides in the same block, index ");
786                    boolean first = true;
787                    for (int i = 1; i <= DSVars.length; i++) {
788                        if (DSVars[i - 1] != null)
789                            continue;
790                        if (!first)
791                            sb.append(", ");
792                        first = false;
793                        sb.append(i);
794                    }
795                    sb.append(" are missing. Set:\n");
796                    sb.append(set);
797                    throw new BLTException(sb.toString());
798                }
799                setCombinations[setCounter] = set.algebraicCombinations();
800                allDynamicStates.addAll(set.fVarsColl());
801                totalNumAlgebraics += set.numAlgebraics();
802                totalNumCombinations *= set.numCombinations();
803                setCounter++;
804            }
805            if (totalNumCombinations > 42)
806                throw new BLTException("Ouch! There are more than 42 combinations for the dynamic states, there were " + totalNumCombinations + " combinations!");
807            FVariable[][] combinations = combineDSCombinations(setCombinations, totalNumAlgebraics);
808            DynamicStateBLT[] blts = new DynamicStateBLT[combinations.length];
809            calculateBlockBLTs(blts, component, producer, stepUtil, combinations, otherVars,
810                    new BLTProducer<DynamicStateBLT>() {
811                @Override
812                public DynamicStateBLT create(FVariable[] combination) {
813                    Set<FVariable> algebraics = new LinkedHashSet<FVariable>(Arrays.asList(combination));
814                    Collection<FVariable> states = new ArrayList<FVariable>();
815                    for (FVariable var : allDynamicStates) {
816                        if (!algebraics.contains(var)) {
817                            states.add(var);
818                        }
819                    }
820                    return new DynamicStateBLT(setVarMap.keySet(), states, algebraics);
821                }
822            });
823            return new DynamicStateBlock(producer, component.computeBlockDependency(), blts, setVarMap.keySet());
824        }
825       
826        interface BLTProducer<B extends BLT> {
827            B create(FVariable[] combination);
828        }
829       
830        public static <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, B extends BLT> void calculateBlockBLTs(B[] blts, SCCBlock<E, V> component, 
831                BlockProducer producer, StepUtil stepUtil, 
832                FVariable[][] combinations, Collection<V> otherVars, BLTProducer<B> bltProducer) {
833            for (int i = 0; i < combinations.length; i++) {
834                FVariable[] combination = combinations[i];
835                StringBuilder sb = new StringBuilder();
836                for (int j = 0; j < combination.length; j++) {
837                    sb.append(combination[j].name() + " ");
838                }
839                ASTNode.log.debug("Generating BLT for: %s", sb);
840                BiPGraph graph = new BiPGraph(component.getMembers(), otherVars);
841                for (FVariable var : combination)
842                    graph.addVariable(var);
843                for (Eq eqn : graph.getEquations()) {
844                    Set<FVariable> vars = eqn.getEquation().referencedFVariables();
845                    for (FVariable var : combination)
846                        if (vars.contains(var))
847                            graph.addEdge(eqn, graph.getVariable(var.name()));
848                }
849                ASTNode.log.debug(graph);
850                graph.maximumMatching(true);
851                B blt = bltProducer.create(combination);
852                if (graph.isComplete()) {
853                    blt = graph.computeBLT(stepUtil, producer, blt, false);
854                } else {
855                    ASTNode.log.verbose("  This combination does not have a valid solution!");
856                    ASTNode.log.debug(graph.printMatchingObj());
857                }
858                ASTNode.log.debug(blt);
859                blts[i] = blt;
860            }
861        }
862    }
863   
864
865}
Note: See TracBrowser for help on using the repository browser.