src/ASTTransform/elementopt.cc

   1 #include "elementopt.h"
   2 #include "csolver.h"
   3 #include "tunable.h"
   4 #include "iterator.h"
   5 #include "boolean.h"
   6 #include "element.h"
   7 #include "predicate.h"
   8 #include "set.h"
   9
  10 ElementOpt::ElementOpt(CSolver *_solver)
  11         : Transform(_solver),
  12           updateSets(false)
  13 {
  14 }
  15
  16 ElementOpt::~ElementOpt() {
  17 }
  18
  19 void ElementOpt::doTransform() {
  20         if (solver->getTuner()->getTunable(ELEMENTOPT, &onoff) == 0)
  21                 return;
  22
  23         //Set once we know we are going to use it.
  24         updateSets = solver->getTuner()->getTunable(ELEMENTOPTSETS, &onoff) == 1;
  25
  26         SetIteratorBooleanEdge *iterator = solver->getConstraints();
  27         while (iterator->hasNext()) {
  28                 BooleanEdge constraint = iterator->next();
  29                 if (constraint->type == PREDICATEOP)
  30                         workList.push((BooleanPredicate *)constraint.getBoolean());
  31         }
  32         while (workList.getSize() != 0) {
  33                 BooleanPredicate *pred = workList.last(); workList.pop();
  34                 processPredicate(pred);
  35         }
  36         delete iterator;
  37 }
  38
  39 void ElementOpt::processPredicate(BooleanPredicate *pred) {
  40         uint numInputs = pred->inputs.getSize();
  41         if (numInputs != 2)
  42                 return;
  43
  44         Predicate *p = pred->getPredicate();
  45         if (p->type == TABLEPRED)
  46                 return;
  47
  48         PredicateOperator *pop = (PredicateOperator *) p;
  49         CompOp op = pop->getOp();
  50
  51         Element *left = pred->inputs.get(0);
  52         Element *right = pred->inputs.get(1);
  53
  54         if (left->type == ELEMCONST) {
  55                 Element *tmp = left;
  56                 left = right;
  57                 right = tmp;
  58                 op = flipOp(op);
  59         } else if (right->type != ELEMCONST)
  60                 return;
  61
  62         if (left->type != ELEMSET)
  63                 return;
  64
  65         if (op == SATC_EQUALS) {
  66                 handlePredicateEquals(pred, (ElementSet *) left, (ElementConst *) right);
  67         } else if (updateSets) {
  68                 handlePredicateInequality(pred, (ElementSet *) left, (ElementConst *) right);
  69         }
  70 }
  71
  72 void ElementOpt::handlePredicateEquals(BooleanPredicate *pred, ElementSet *left, ElementConst *right) {
  73         if (pred->isTrue()) {
  74                 replaceVarWithConst(pred, left, right);
  75         } else if (pred->isFalse() && updateSets) {
  76                 constrainVarWithConst(pred, left, right);
  77         }
  78 }
  79
  80 void ElementOpt::handlePredicateInequality(BooleanPredicate *pred, ElementSet *var, ElementConst *value) {
  81         Predicate *p = pred->getPredicate();
  82         PredicateOperator *pop = (PredicateOperator *) p;
  83         CompOp op = pop->getOp();
  84
  85         if (pred->isFalse()) {
  86                 op = negateOp(op);
  87         } else if (!pred->isTrue()) {
  88                 ASSERT(0);
  89         }
  90
  91         Set *s = var->getRange();
  92         if (s->isRange)
  93                 return;
  94
  95         uint size = s->getSize();
  96         uint64_t elemArray[size];
  97         uint count = 0;
  98         uint64_t cvalue = value->value;
  99
 100         switch (op) {
 101         case SATC_LT: {
 102                 for (uint i = 0; i < size; i++) {
 103                         uint64_t val = s->getElement(i);
 104                         if (val < cvalue)
 105                                 elemArray[count++] = val;
 106                 }
 107                 break;
 108         }
 109         case SATC_GT: {
 110                 for (uint i = 0; i < size; i++) {
 111                         uint64_t val = s->getElement(i);
 112                         if (val > cvalue)
 113                                 elemArray[count++] = val;
 114                 }
 115                 break;
 116         }
 117         case SATC_LTE: {
 118                 for (uint i = 0; i < size; i++) {
 119                         uint64_t val = s->getElement(i);
 120                         if (val <= cvalue)
 121                                 elemArray[count++] = val;
 122                 }
 123                 break;
 124         }
 125         case SATC_GTE: {
 126                 for (uint i = 0; i < size; i++) {
 127                         uint64_t val = s->getElement(i);
 128                         if (val >= cvalue)
 129                                 elemArray[count++] = val;
 130                 }
 131                 break;
 132         }
 133
 134         default:
 135                 ASSERT(0);
 136         }
 137         if (size == count)
 138                 return;
 139
 140         Set *newset = solver->createSet(s->type, elemArray, count);
 141         solver->elemMap.remove(var);
 142         var->set = newset;
 143         solver->elemMap.put(var, var);
 144
 145         if (count == 1) {
 146                 ElementConst *elemconst = (ElementConst *) solver->getElementConst(s->type, elemArray[0]);
 147                 replaceVarWithConst(pred, var, elemconst);
 148         }
 149 }
 150
 151 void ElementOpt::constrainVarWithConst(BooleanPredicate *pred, ElementSet *var, ElementConst *value) {
 152         Set *s = var->getRange();
 153         if (s->isRange)
 154                 return;
 155         uint size = s->getSize();
 156         uint64_t elemArray[size];
 157         uint count = 0;
 158         uint64_t cvalue = value->value;
 159         for (uint i = 0; i < size; i++) {
 160                 uint64_t val = s->getElement(i);
 161                 if (val != cvalue)
 162                         elemArray[count++] = val;
 163         }
 164         if (size == count)
 165                 return;
 166
 167         Set *newset = solver->createSet(s->type, elemArray, count);
 168         solver->elemMap.remove(var);
 169         var->set = newset;
 170         solver->elemMap.put(var, var);
 171
 172         if (count == 1) {
 173                 ElementConst *elemconst = (ElementConst *) solver->getElementConst(s->type, elemArray[0]);
 174                 replaceVarWithConst(pred, var, elemconst);
 175         }
 176 }
 177
 178 void ElementOpt::replaceVarWithConst(BooleanPredicate *pred, ElementSet *var, ElementConst *value) {
 179         uint size = var->parents.getSize();
 180         for (uint i = 0; i < size; i++) {
 181                 ASTNode *parent = var->parents.get(i);
 182                 if (parent->type == PREDICATEOP && pred != parent) {
 183                         BooleanPredicate *newpred = (BooleanPredicate *) parent;
 184                         for (uint j = 0; j < newpred->inputs.getSize(); j++) {
 185                                 Element *e = newpred->inputs.get(j);
 186                                 if (e == var) {
 187                                         solver->boolMap.remove(newpred);
 188                                         newpred->inputs.set(j, value);
 189                                         solver->boolMap.put(newpred, newpred);
 190                                         if (newpred->isTrue() || newpred->isFalse())
 191                                                 workList.push(newpred);
 192                                         break;
 193                                 }
 194                         }
 195                 }
 196         }
 197 }