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