tgt-vvp/vector.c

   1 /*
   2  * Copyright (c) 2002 Stephen Williams (steve@icarus.com)
   3  *
   4  *    This source code is free software; you can redistribute it
   5  *    and/or modify it in source code form under the terms of the GNU
   6  *    General Public License as published by the Free Software
   7  *    Foundation; either version 2 of the License, or (at your option)
   8  *    any later version.
   9  *    This program is distributed in the hope that it will be useful,
  10  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *    GNU General Public License for more details.
  13  *
  14  *    You should have received a copy of the GNU General Public License
  15  *    along with this program; if not, write to the Free Software
  16  *    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
  17  */
  18 #ifdef HAVE_CVS_IDENT
  19 #ident "$Id: vector.c,v 1.15 2007/04/01 05:26:17 steve Exp $"
  20 #endif
  21
  22 # include  "vvp_priv.h"
  23 # include  <assert.h>
  24
  25 /* Maximum vector bits in a thread. If a thread co-processor is
  26  * implemented, this value may need to be reduced. At that time
  27  * wider operations will need to be partitioned. For example
  28  * shift operations on WIDE (say > 64k bit) registers.
  29  */
  30 #define MAX_VEC (256*1024)
  31
  32 static struct allocation_score_s {
  33       ivl_expr_t exp;
  34       ivl_signal_t sig;
  35       unsigned sig_word;
  36       unsigned  exp_bit : 24;
  37       unsigned  sig_bit : 24;
  38       unsigned alloc    :  8;
  39 } allocation_map[MAX_VEC] = { {0} };
  40
  41 /* This is the largest bit to have lookaside values. */
  42 static unsigned lookaside_top = 0;
  43
  44 static inline ivl_expr_t peek_exp(unsigned addr)
  45 {
  46       return allocation_map[addr].exp;
  47 }
  48
  49 static inline unsigned peek_exp_bit(unsigned addr)
  50 {
  51       return allocation_map[addr].exp_bit;
  52 }
  53
  54 static inline void set_exp(unsigned addr, ivl_expr_t exp, unsigned ebit)
  55 {
  56       allocation_map[addr].exp = exp;
  57       allocation_map[addr].exp_bit = ebit;
  58 }
  59
  60 static inline void set_sig(unsigned addr, ivl_signal_t exp, unsigned sig_word, unsigned ebit)
  61 {
  62       allocation_map[addr].sig = exp;
  63       allocation_map[addr].sig_word = sig_word;
  64       allocation_map[addr].sig_bit = ebit;
  65 }
  66
  67 /*
  68  * This clears a vector that was previously allocated by
  69  * allocate_vector. That is, it unmarks all the bits of the map that
  70  * represent this vector.
  71  *
  72  * If the vector is based in one of 4 constant bit values, then there
  73  * are no bits to clear. If the vector is based in the 4-8 result
  74  * area, then someone is broken.
  75  */
  76 void clr_vector(struct vector_info vec)
  77 {
  78       unsigned idx;
  79       if (vec.base < 4)
  80             return;
  81       assert(vec.base >= 8);
  82       for (idx = 0 ;  idx < vec.wid ;  idx += 1) {
  83             assert( allocation_map[vec.base+idx].alloc > 0);
  84             allocation_map[vec.base+idx].alloc -= 1;
  85       }
  86 }
  87
  88 static unsigned allocate_vector_no_lookaside(unsigned wid, int skip_lookaside)
  89 {
  90       unsigned base = 8;
  91       unsigned idx = 0;
  92
  93       while (idx < wid) {
  94             assert((base + idx) < MAX_VEC);
  95             if ((allocation_map[base+idx].alloc > 0)
  96                 || (skip_lookaside && peek_exp(base+idx))) {
  97                   base = base + idx + 1;
  98                   idx = 0;
  99
 100             } else {
 101                   idx += 1;
 102             }
 103       }
 104
 105       for (idx = 0 ;  idx < wid ;  idx += 1) {
 106             allocation_map[base+idx].alloc += 1;
 107             set_exp(base+idx, 0, 0);
 108             set_sig(base+idx, 0, 0, 0);
 109       }
 110
 111       return base;
 112 }
 113
 114 /*
 115  * This unconditionally allocates a stretch of bits from the register
 116  * set. It never returns a bit addressed <8 (0-3 are constant, 4-7 are
 117  * condition codes).
 118  *
 119  * First try to allocate a vector without interfering with any bits
 120  * cached by the lookaside buffer. If that doesn't work, then try
 121  * again without worrying about trashing lookaside results. This
 122  * should lead to preferentially allocating new bits instead of
 123  * constantly overwriting intermediate results.
 124  */
 125 unsigned allocate_vector(unsigned wid)
 126 {
 127       unsigned base = allocate_vector_no_lookaside(wid, 1);
 128
 129       if (base == 0)
 130             base = allocate_vector_no_lookaside(wid, 0);
 131       return base;
 132 }
 133
 134 /*
 135  * This clears the expression cache of the allocation map. It is
 136  * called to prevent reuse of existing expressions, normally at the
 137  * start of a basic block, but also at the end of thread processing.
 138  */
 139 void clear_expression_lookaside(void)
 140 {
 141       unsigned idx;
 142
 143       for (idx = 0 ;  idx < lookaside_top ;  idx += 1) {
 144             set_exp(idx, 0, 0);
 145             set_sig(idx, 0, 0, 0);
 146       }
 147
 148       lookaside_top = 0;
 149 }
 150
 151 static int test_expression_savable(ivl_expr_t exp)
 152 {
 153       switch (ivl_expr_type(exp)) {
 154
 155           case IVL_EX_NUMBER:
 156           case IVL_EX_STRING:
 157             return 1;
 158
 159           default:
 160             return 0;
 161       }
 162 }
 163
 164 void save_expression_lookaside(unsigned addr, ivl_expr_t exp, unsigned wid)
 165 {
 166       unsigned idx;
 167       assert(addr >= 8);
 168       assert((addr+wid) <= MAX_VEC);
 169
 170         /* When saving an expression to the lookaside, also clear the
 171            signal saved in the lookaside for these bits. The reason is
 172            that an expression calculation will replace any signal
 173            bits. */
 174       for (idx = 0 ;  idx < wid ;  idx += 1)
 175             set_sig(addr+idx, 0, 0, 0);
 176
 177         /* Only certain types of expressions are savable. */
 178       if ( ! test_expression_savable(exp))
 179             return;
 180
 181       for (idx = 0 ;  idx < wid ;  idx += 1) {
 182             set_exp(addr+idx, exp, idx);
 183       }
 184
 185       if ((addr+wid) > lookaside_top)
 186             lookaside_top = addr+wid;
 187 }
 188
 189 static void clear_signal_lookaside_bit(unsigned idx, ivl_signal_t sig, unsigned sig_word)
 190 {
 191       if (allocation_map[idx].alloc > 0)
 192             return;
 193       if (allocation_map[idx].sig != sig)
 194             return;
 195       if (allocation_map[idx].sig_word != sig_word)
 196             return;
 197
 198       set_sig(idx, 0, 0, 0);
 199 }
 200
 201 void save_signal_lookaside(unsigned addr, ivl_signal_t sig, unsigned sig_word, unsigned wid)
 202 {
 203       unsigned idx;
 204         /* Don't bind any of the low bits to a signal. */
 205       if (addr < 8 && wid > 0)
 206             return;
 207
 208       assert((addr+wid) <= MAX_VEC);
 209
 210       for (idx = 8 ;  idx < addr ;  idx += 1)
 211             clear_signal_lookaside_bit(idx, sig, sig_word);
 212
 213       for (idx = 0 ;  idx < wid ;  idx += 1)
 214             set_sig(addr+idx, sig, sig_word, idx);
 215
 216       if ((addr+wid) > lookaside_top)
 217             lookaside_top = addr+wid;
 218
 219       for (idx = addr+wid ;  idx < lookaside_top ;  idx += 1)
 220             clear_signal_lookaside_bit(idx, sig, sig_word);
 221 }
 222
 223 static int compare_exp(ivl_expr_t l, ivl_expr_t r)
 224 {
 225       if (! (l && r))
 226             return 0;
 227       if (l == r)
 228             return 1;
 229
 230       if (ivl_expr_type(l) != ivl_expr_type(r))
 231             return 0;
 232
 233       switch (ivl_expr_type(l)) {
 234
 235           case IVL_EX_NUMBER:
 236             if (ivl_expr_width(l) != ivl_expr_width(r))
 237                   return 0;
 238             { const char*bitl = ivl_expr_bits(l);
 239               const char*bitr = ivl_expr_bits(r);
 240               unsigned idx;
 241               for (idx = 0 ;  idx < ivl_expr_width(l) ;  idx += 1) {
 242                     if (bitl[idx] != bitr[idx])
 243                           return 0;
 244               }
 245             }
 246             return 1;
 247
 248           case IVL_EX_SELECT:
 249             if (! compare_exp(ivl_expr_oper1(l), ivl_expr_oper1(r)))
 250                   return 0;
 251
 252             if (ivl_expr_oper2(l) == 0 && ivl_expr_oper1(r) == 0)
 253                   return 1;
 254
 255             if (! compare_exp(ivl_expr_oper2(l), ivl_expr_oper2(r)))
 256                   return 0;
 257
 258             return 1;
 259
 260           case IVL_EX_SIGNAL:
 261             if (ivl_expr_signal(l) != ivl_expr_signal(r))
 262                   return 0;
 263
 264             if (ivl_expr_width(l) != ivl_expr_width(r))
 265                   return 0;
 266
 267               /* Don't match array words. */
 268             if (ivl_expr_oper1(l) || ivl_expr_oper1(r))
 269                   return 0;
 270
 271             return 1;
 272
 273           default:
 274             break;
 275       }
 276
 277       return 0;
 278 }
 279
 280 static unsigned find_expression_lookaside(ivl_expr_t exp, unsigned wid)
 281 {
 282       unsigned top;
 283       unsigned idx, match;
 284       ivl_signal_t sig;
 285
 286       if (lookaside_top <= wid)
 287             return 0;
 288
 289       top = lookaside_top - wid + 1;
 290
 291         /* Look in the expression lookaside for this expression. */
 292       assert(exp);
 293       match = 0;
 294       for (idx = 8 ;  idx < lookaside_top ;  idx += 1) {
 295             if (! compare_exp(allocation_map[idx].exp, exp)) {
 296                   match = 0;
 297                   continue;
 298             }
 299
 300             if (allocation_map[idx].exp_bit != match) {
 301                   match = 0;
 302                   continue;
 303             }
 304
 305             match += 1;
 306             if (match == wid)
 307                   return idx-match+1;
 308       }
 309
 310         /* The general expression lookup failed. If this is an
 311            IVL_EX_SIGNAL, then look again in the variable lookaside
 312            (which is saved l-values) for the expression. */
 313       if (ivl_expr_type(exp) != IVL_EX_SIGNAL)
 314             return 0;
 315
 316       sig = ivl_expr_signal(exp);
 317
 318         /* Only reg signals (variables) will be in the signal
 319            lookaside, because only blocking assigned values are in the
 320            signal lookaside. */
 321       if (ivl_signal_type(sig) != IVL_SIT_REG)
 322             return 0;
 323
 324         /* Now look for signal value matches in the signal lookaside. */
 325       match = 0;
 326       for (idx = 8 ;  idx < lookaside_top ;  idx += 1) {
 327             if (sig != allocation_map[idx].sig) {
 328                   match = 0;
 329                   continue;
 330             }
 331
 332             if (allocation_map[idx].sig_bit != match) {
 333                   match = 0;
 334                   continue;
 335             }
 336
 337             match += 1;
 338             if (match == wid)
 339                   return idx-match+1;
 340
 341       }
 342
 343       return 0;
 344 }
 345
 346 /*
 347  * Look for the expression in the expression lookaside table. If it is
 348  * there, then allocate it and return the base. In this case the
 349  * caller will not need to evaluate the expression. If this function
 350  * returns 0, then the expression is not found and nothing is allocated.
 351  */
 352 unsigned allocate_vector_exp(ivl_expr_t exp, unsigned wid,
 353                              int exclusive_flag)
 354 {
 355       unsigned idx;
 356       unsigned la = find_expression_lookaside(exp, wid);
 357       if (la == 0)
 358             return 0;
 359
 360       if (exclusive_flag) {
 361               /* If the caller is requesting exclusive allocation of
 362                  the expression, then return not-found if a lookup
 363                  already matched the expression. */
 364             for (idx = 0 ;  idx < wid ;  idx += 1)
 365                   if (allocation_map[la+idx].alloc)
 366                         return 0;
 367       }
 368
 369       for (idx = 0 ;  idx < wid ;  idx += 1)
 370             allocation_map[la+idx].alloc += 1;
 371
 372       return la;
 373 }
 374
 375 /*
 376  * $Log: vector.c,v $
 377  * Revision 1.15  2007/04/01 05:26:17  steve
 378  *  Fix that save expression lookaside always clears cached variable values.
 379  *
 380  * Revision 1.14  2007/03/22 16:08:18  steve
 381  *  Spelling fixes from Larry
 382  *
 383  * Revision 1.13  2007/03/20 04:26:56  steve
 384  *  Clear lookaside even if source bit is a constant.
 385  *
 386  * Revision 1.12  2007/02/26 19:49:50  steve
 387  *  Spelling fixes (larry doolittle)
 388  *
 389  * Revision 1.11  2007/02/06 04:43:53  steve
 390  *  Expression lookaside cannot hold complex expressions
 391  *
 392  * Revision 1.10  2007/01/19 02:30:19  steve
 393  *  Fix bad lookaside references in vvp thread code generator.
 394  *
 395  * Revision 1.9  2007/01/18 00:59:48  steve
 396  *  Do not match array words in expression lookaside.
 397  *
 398  * Revision 1.8  2007/01/16 05:44:16  steve
 399  *  Major rework of array handling. Memories are replaced with the
 400  *  more general concept of arrays. The NetMemory and NetEMemory
 401  *  classes are removed from the ivl core program, and the IVL_LPM_RAM
 402  *  lpm type is removed from the ivl_target API.
 403  *
 404  * Revision 1.7  2005/09/17 01:01:00  steve
 405  *  More robust use of precalculated expressions, and
 406  *  Separate lookaside for written variables that can
 407  *  also be reused.
 408  *
 409  * Revision 1.6  2005/09/15 02:50:13  steve
 410  *  Preserve precalculated expressions when possible.
 411  *
 412  * Revision 1.5  2005/01/24 05:08:02  steve
 413  *  Part selects are done in the compiler, not here.
 414  *
 415  * Revision 1.4  2003/07/03 17:44:10  steve
 416  *  Wider thread vector limit.
 417  *
 418  * Revision 1.3  2003/06/17 19:17:42  steve
 419  *  Remove short int restrictions from vvp opcodes.
 420  *
 421  * Revision 1.2  2003/06/05 04:18:50  steve
 422  *  Better width testing for thread vector allocation.
 423  *
 424  * Revision 1.1  2002/09/27 16:33:34  steve
 425  *  Add thread expression lookaside map.
 426  *
 427  */
 428