View Javadoc

1   // BDDInterpreter.java, created Mar 16, 2004 12:49:19 PM 2004 by mcarbin
2   // Copyright (C) 2004 Michael Carbin
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package net.sf.bddbddb.ir;
5   
6   import java.util.Iterator;
7   import net.sf.bddbddb.BDDRelation;
8   import net.sf.bddbddb.BDDSolver;
9   import net.sf.bddbddb.InferenceRule;
10  import net.sf.bddbddb.IterationList;
11  import net.sf.bddbddb.Relation;
12  import net.sf.javabdd.BDD;
13  
14  /***
15   * BDDInterpreter
16   * 
17   * @author mcarbin
18   * @version $Id: BDDInterpreter.java 522 2005-04-29 02:34:44Z joewhaley $
19   */
20  public class BDDInterpreter extends Interpreter {
21      /***
22       * @param ir
23       */
24      public BDDInterpreter(IR ir) {
25          this.ir = ir;
26          if (ir != null) {
27              opInterpreter = new BDDOperationInterpreter((BDDSolver) ir.solver, ((BDDSolver) ir.solver).getBDDFactory());
28          }
29      }
30      public void interpret() {
31          if (ir.DOMAIN_ASSIGNMENT)
32              ((BDDOperationInterpreter)opInterpreter).needsDomainMatch = false;
33          interpret(ir.graph.getIterationList());
34      }
35  
36      int MAX_ITERATIONS = 128;
37      
38      public boolean interpret(IterationList list) {
39          boolean everChanged = false;
40          boolean change;
41          int iterations = 0;
42          for (;;) {
43              ++iterations;
44              change = false;
45              for (Iterator i = list.iterator(); i.hasNext();) {
46                  Object o = i.next();
47                  if (TRACE) System.out.println(o);
48                  if (o instanceof IterationList) {
49                      IterationList sublist = (IterationList) o;
50                      if (interpret(sublist)) {
51                          change = true;
52                      }
53                  } else if (o instanceof Operation) {
54                      Operation op = (Operation) o;
55                      BDDRelation dest = (BDDRelation) op.getRelationDest();
56                      BDD oldValue = null;
57                      Relation changed = null;
58                      if (!change && dest != null && dest.getBDD() != null) {
59                          oldValue = dest.getBDD().id();
60                          changed = dest;
61                      }
62                      op.visit(opInterpreter);
63                      if (oldValue != null) {
64                          change = !oldValue.equals(dest.getBDD());
65                          if (TRACE && change) System.out.println(changed + " Changed!");
66                          oldValue.free();
67                      }
68                  } else if (o instanceof InferenceRule) {
69                      InferenceRule ir = (InferenceRule) o;
70                      if (ir.update()) {
71                          change = true;
72                      }
73                  }
74              }
75              if (!change) break;
76              everChanged = true;
77              if (!list.isLoop()) break;
78              if (iterations == MAX_ITERATIONS) break;
79              interpret(list.getLoopEdge());
80          }
81          return everChanged;
82      }
83  }