srel.cc

   1 #include "srel.h"
   2 #include "domain.h"
   3
   4 #include <vector>
   5 #include <algorithm>
   6
   7 typedef std::vector<Variable_ID> varvector;
   8
   9 SRelation::SRelation (int in, int out, std::vector< std::vector<int> > & c,
  10     symtab_ann *a) : Relation(in, out), sa(a)
  11 {
  12     assert(c.size() >= 1);
  13     int dim = c[0].size();
  14     varvector vars;
  15
  16     for (int j = 1; j <= n_inp(); ++j)
  17         vars.push_back(input_var(j));
  18     for (int j = 1; j <= n_out(); ++j)
  19         vars.push_back(output_var(j));
  20     assert(in + out + 2 == dim);
  21
  22     F_And *base = add_and();
  23     for (int i = 0; i < c.size(); ++i) {
  24         Constraint_Handle h;
  25         if (c[i][0])
  26             h = base->add_GEQ();
  27         else
  28             h = base->add_EQ();
  29         for (int j = 1; j < dim-1; ++j)
  30             h.update_coef(vars[j-1], c[i][j]);
  31         h.update_const(c[i][dim-1]);
  32     }
  33     finalize();
  34 }
  35
  36 void SRelation::fix(var_sym *var, int val)
  37 {
  38     sa->add_var(var);
  39     EQ_Handle e = and_with_EQ();
  40     e.update_coef(get_local(sa->vars[var]), -1);
  41     e.update_const(val);
  42 }
  43
  44 /* Add constraint "var >= 0" */
  45 void SRelation::set_infinite(var_sym *var)
  46 {
  47     sa->add_var(var);
  48     GEQ_Handle e = and_with_GEQ();
  49     e.update_coef(get_local(sa->vars[var]), 1);
  50 }
  51
  52 void SRelation::intersect(named_lin_ineq *nlq)
  53 {
  54     for (int i = 1; i < nlq->n(); ++i)
  55         sa->add_var(nlq->names()[i].var());
  56
  57     integer_matrix lq = nlq->ineqs();
  58     for (int i = 0; i < lq.m(); ++i) {
  59         GEQ_Handle g = and_with_GEQ();
  60         g.update_const(lq[i][0]);
  61         for (int j = 1; j < lq.n(); ++j) {
  62             g.update_coef(get_local(sa->vars[nlq->names()[j].var()]), lq[i][j]);
  63         }
  64     }
  65     delete nlq;
  66 }
  67
  68 static void print_constraint(Constraint_Handle c, varvector& vv, int geq)
  69 {
  70     printf(" %6d", geq);
  71     for (int i = 0; i < vv.size(); ++i)
  72         printf(" " coef_fmt, c.get_coef(vv[i]));
  73     printf(" " coef_fmt, c.get_const());
  74     printf("\n");
  75 }
  76
  77 static bool equal(operand op1, operand op2)
  78 {
  79     if (op1.kind() != op2.kind())
  80         return false;
  81     switch (op1.kind()) {
  82     case OPER_INSTR: {
  83         if (op1.instr()->opcode() != op2.instr()->opcode())
  84             return false;
  85         if (op1.instr()->opcode() == io_ldc) {
  86             in_ldc *in1 = dynamic_cast<in_ldc *>(op1.instr());
  87             in_ldc *in2 = dynamic_cast<in_ldc *>(op2.instr());
  88             if (in1->value() != in2->value())
  89                 return false;
  90         }
  91         for (unsigned n = 0; n < op1.instr()->num_srcs(); n++) {
  92             if (!equal(op1.instr()->src_op(n), op2.instr()->src_op(n)))
  93                 return false;
  94         }
  95         break;
  96     }
  97     case OPER_SYM:
  98         return op1.symbol() == op2.symbol();
  99     case OPER_NULL:
 100         return true;
 101     default:
 102         return false;
 103     }
 104     return true;
 105 }
 106
 107 /* Set nested accesses of d to the union of those in a and b,
 108  * unifying accesses that have identical operations.
 109  */
 110 static SRelation *set_nested(SRelation *d, SRelation *a, SRelation *b)
 111 {
 112         for (int i = 0; i < a->nested.size(); ++i)
 113                 d->nested.push_back(a->nested[i]);
 114         for (int i = 0; i < b->nested.size(); ++i) {
 115                 int j;
 116                 for (j = 0; j < d->nested.size(); ++j) {
 117                         if (b->nested[i] == d->nested[j])
 118                                 break;
 119                         if (b->nested[i]->op.is_null())
 120                                 continue;
 121                         if (d->nested[j]->op.is_null())
 122                                 continue;
 123                         if (equal(b->nested[i]->op, d->nested[j]->op)) {
 124                                 Relation r = copy(*(Relation*)d);
 125                                 EQ_Handle e = r.and_with_EQ();
 126                                 e.update_coef(r.get_local(d->sa->vars[b->nested[i]->var]), -1);
 127                                 e.update_coef(r.get_local(d->sa->vars[d->nested[j]->var]), 1);
 128                                 r = Project(r, d->sa->vars[b->nested[i]->var]);
 129                                 SRelation *p = new SRelation(r, d->sa, d->nested);
 130                                 delete d;
 131                                 d = p;
 132                                 break;
 133                         }
 134                 }
 135                 if (j == d->nested.size())
 136                         d->nested.push_back(b->nested[i]);
 137         }
 138
 139         return d;
 140 }
 141
 142 SRelation * SRelation::Intersection(SRelation *b)
 143 {
 144     Relation I = ::Intersection(copy(*(Relation*) this), copy(*(Relation*) b));
 145     SRelation *c = new SRelation(I, sa);
 146     c = set_nested(c, this, b);
 147     return c;
 148 }
 149
 150 SRelation * SRelation::Union(SRelation *b)
 151 {
 152     Relation I = ::Union(copy(*(Relation*) this), copy(*(Relation*) b));
 153     SRelation *u = new SRelation(I, sa);
 154     u = set_nested(u, this, b);
 155     return u;
 156 }
 157
 158 SRelation * SRelation::Difference(SRelation *b)
 159 {
 160     Relation I = ::Difference(copy(*(Relation*) this), copy(*(Relation*) b));
 161     SRelation *d = new SRelation(I, sa);
 162     d = set_nested(d, this, b);
 163     return d;
 164 }
 165
 166 SRelation * SRelation::Composition(SRelation *b)
 167 {
 168     Relation I = ::Composition(copy(*(Relation*) this), copy(*(Relation*) b));
 169     return new SRelation(I, sa);
 170 }
 171
 172 SRelation * SRelation::Complement()
 173 {
 174     Relation I = ::Complement(copy(*(Relation*) this));
 175     return new SRelation(I, sa, nested);
 176 }