src/baseparsuif/dependence/access_vector.h

   1
   2 /* file "access_vector.h" */
   3
   4 /*  Copyright (c) 1994 Stanford University
   5
   6     All rights reserved.
   7
   8     This software is provided under the terms described in
   9     the "suif_copyright.h" include file. */
  10
  11 #include <suif_copyright.h>
  12
  13 #pragma interface
  14
  15 #ifndef ACCESS_VECTOR
  16 #define ACCESS_VECTOR
  17
  18 class tree_node;
  19 class tree_instr;
  20 class tree_node_list;
  21 class tree_proc;
  22
  23
  24 // stupid c++ won't let this be a static class member
  25 extern int forget_about_mod_this;
  26
  27 class access_vector;
  28
  29 class av_compare_info {
  30     int flag;
  31 public:
  32     av_compare_info(const access_vector *, const access_vector *);
  33     int same_indregs() {return flag&1;}
  34     int same_conregs() {return (flag>>1)&1;}
  35     int same_memregs() {return (flag>>2)&1;}
  36     int same_paths() {return (flag>>3)&1;}
  37     int same_const() {return (flag>>4)&1;}
  38     int identical() {return (flag&31) == 31;}
  39     int identical_excluding_const() {return (flag&15) == 15;}
  40 };
  41
  42 struct access_list_e: public ass_list_e<int> {
  43 friend class access_list;
  44 friend class access_vector;
  45     access_list_e(void *v,int i): ass_list_e<int>(v, i) {}
  46     ~access_list_e() {}
  47     const void *var() {return key;}
  48     int val() {return info;}
  49 };
  50
  51
  52 struct access_list: public ass_list<int> {
  53     access_list() {}
  54     access_list_e *search(const void *v) const
  55              {return (access_list_e *) ass_list<int>::search(v);}
  56     int val(const void *v) const
  57              {access_list_e *e=search(v); return e ? e->val() : 0;}
  58     int count();
  59     void enter(const void *v,int i);  // compiler bug, can't inline
  60     access_list_e *pop() {return (access_list_e *) ass_list<int>::pop();}
  61     void intersect(access_list *a1, access_list *a2);
  62     void intersect(access_list *a1);
  63     void unite(access_list *a1, access_list *a2);
  64     void unite(access_list *a1);
  65 };
  66
  67 struct access_list_iter: public ass_list_iter<int> {
  68     access_list_iter(const access_list *c): ass_list_iter<int>(c) {}
  69     ~access_list_iter() {}
  70     access_list_e *step() {return (access_list_e *) ass_list_iter<int>::step();}
  71     int is_empty() {return ass_list_iter<int>::is_empty();}
  72     void print(FILE *f=stdout);
  73 };
  74
  75 // this holds the information for one index
  76
  77 class access_vector: public glist_e {
  78     friend int av_compare_access_lists(const access_list *,
  79                                        const access_list *);
  80     void normalize_step_ref(access_list_e *);
  81     void enter_als(const access_vector *);
  82 public:
  83     int too_messy;              // if not a perfect access vector
  84     access_list elts;           // access vector itself (for induction vars)
  85     access_list conregs;        // access vector for non-induction registers
  86     access_list memregs;        // access vector for indirections thru regs
  87     int con;                    // constant to add to vector
  88     tree_for *mod_this;         // innermost for which defines a variable in
  89     // this access vector (may make conserv assump)
  90     // nil means this is completely loop constant
  91     // if not enclosed in a for loop, also nil
  92     // ignores references to induction variables
  93     void set_mod_this(tree_node * ti);
  94     int *min, *max;             // min and max values for this dimension
  95     void set_min_max();         // set these values
  96     access_vector(): glist_e(),too_messy(0),con(0),mod_this(0),min(0),max(0) {}
  97     access_vector(const access_vector &);
  98     access_vector(tree_instr * n, int fancy=TRUE);
  99     access_vector(operand op, tree_node * tn, int fancy=TRUE);
 100     access_vector(instruction * inst, int fancy=TRUE);
 101     access_vector(const access_vector *);
 102     ~access_vector();
 103     int val(tree_node *a) {return elts.val(a);}
 104     int val(var_sym * s, int indirect)
 105         {access_list *l = (indirect) ? &memregs : &conregs;
 106          return l->val((void *)s);}
 107     void add(tree_node *a, int i) {elts.enter(a,i);}
 108     void add(var_sym * s, int indirect, int i)  {
 109         access_list *l = (indirect) ? &memregs : &conregs;
 110         l->enter(s, i);}
 111     int is_const() { return (!too_messy && elts.is_empty() &&
 112                              conregs.is_empty() && memregs.is_empty()); }
 113
 114     void print(FILE *f=stdout);
 115     void normalize_step_ref();  //normalize so equiv to loop stp=1
 116     operand generate_code(tree_proc *p, block_symtab * sym = NULL);
 117     int operator ==(const access_vector &a)
 118         {class av_compare_info ci(this,&a);
 119          return ci.identical();}
 120     int operator !=(const access_vector &a)
 121         {return !(*this==a);}
 122     void operator =(const access_vector &);
 123     void operator += (const access_vector &a);
 124     void operator -= (const access_vector &a);
 125     void operator *= (int f);
 126     void operator /= (int f);
 127     access_vector operator +(const access_vector &a)
 128         {access_vector tmp(*this); tmp += a; return tmp;}
 129     access_vector operator -(const access_vector &a)
 130         {access_vector tmp(*this); tmp -= a; return tmp;}
 131     access_vector operator -()
 132         {access_vector tmp(*this); tmp *= -1; return tmp;}
 133     friend inline access_vector operator *(int f,const access_vector &a);
 134     friend inline access_vector operator *(const access_vector &a,int f);
 135     friend inline access_vector operator /(const access_vector &a,int f);
 136 };
 137
 138 inline access_vector operator *(int f,const access_vector &a)
 139 {access_vector tmp(a); tmp *= f; return tmp;}
 140 inline access_vector operator *(const access_vector &a,int f)
 141 {access_vector tmp(a); tmp *= f; return tmp;}
 142 inline access_vector operator /(const access_vector &a,int f)
 143 {access_vector tmp(a); tmp /= f; return tmp;}
 144
 145 // a list of access vectors, one for each index of the array (in order)
 146 class array_info: public glist {
 147 private:
 148     /* We make explicit copy constructor and assignment operator and
 149      * make them private to foil C++'s automatic default versions. */
 150     array_info(const array_info &)  { assert(FALSE); }
 151     void operator=(const array_info &)  { assert(FALSE); }
 152 public:
 153     array_info(): glist() {}
 154     array_info(instruction * ins, int fancy=TRUE);
 155     array_info(array_info *);
 156     ~array_info();
 157     access_vector *pop() {return (access_vector *) glist::pop();}
 158     void append(access_vector *a) {glist::append((glist_e *)a);}
 159     int is_empty() {return glist::is_empty();}
 160     int count() {return glist::count();}
 161     void print(FILE *f=stdout);
 162     void normalize_step_ref();  //normalize so equiv to loop step=1
 163     access_vector *first() {return (access_vector *) glist::head();}
 164     access_vector *last() {return (access_vector *) glist::tail();}
 165 };
 166
 167 // the iterator, to examine the access vector for each index in turn
 168 class array_info_iter: public glist_iter {
 169 public:
 170     array_info_iter(array_info *v): glist_iter((glist *)v) {}
 171     ~array_info_iter() {}
 172     access_vector *step()
 173         {return (access_vector *) glist_iter::step();}
 174     access_vector *next()
 175         {return (access_vector *) glist_iter::nxt;}
 176     int is_empty() {return glist_iter::is_empty();}
 177 };
 178
 179 void normalize_step_loops(array_info *,array_info *,
 180                           access_vector *, tree_for_test);
 181 void normalize_test(array_info *, array_info  *,access_vector *,
 182                     tree_for_test);
 183
 184 #endif /* ACCESS_VECTOR */