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             if (base+idx >= MAX_VEC)
  95                   return 0;
  96
  97             assert((base + idx) < MAX_VEC);
  98             if ((allocation_map[base+idx].alloc > 0)
  99                 || (skip_lookaside && peek_exp(base+idx))) {
 100                   base = base + idx + 1;
 101                   idx = 0;
 102
 103             } else {
 104                   idx += 1;
 105             }
 106       }
 107
 108       for (idx = 0 ;  idx < wid ;  idx += 1) {
 109             allocation_map[base+idx].alloc += 1;
 110             set_exp(base+idx, 0, 0);
 111             set_sig(base+idx, 0, 0, 0);
 112       }
 113
 114       return base;
 115 }
 116
 117 /*
 118  * This unconditionally allocates a stretch of bits from the register
 119  * set. It never returns a bit addressed <8 (0-3 are constant, 4-7 are
 120  * condition codes).
 121  *
 122  * First try to allocate a vector without interfering with any bits
 123  * cached by the lookaside buffer. If that doesn't work, then try
 124  * again without worrying about trashing lookaside results. This
 125  * should lead to preferentially allocating new bits instead of
 126  * constantly overwriting intermediate results.
 127  *
 128  * If there is no space for a vector of the given width, then give up
 129  * and return 0.
 130  */
 131 unsigned allocate_vector(unsigned wid)
 132 {
 133       unsigned base = allocate_vector_no_lookaside(wid, 1);
 134
 135       if (base == 0)
 136             base = allocate_vector_no_lookaside(wid, 0);
 137       return base;
 138 }
 139
 140 /*
 141  * This clears the expression cache of the allocation map. It is
 142  * called to prevent reuse of existing expressions, normally at the
 143  * start of a basic block, but also at the end of thread processing.
 144  */
 145 void clear_expression_lookaside(void)
 146 {
 147       unsigned idx;
 148
 149       for (idx = 0 ;  idx < lookaside_top ;  idx += 1) {
 150             set_exp(idx, 0, 0);
 151             set_sig(idx, 0, 0, 0);
 152       }
 153
 154       lookaside_top = 0;
 155 }
 156
 157 static int test_expression_savable(ivl_expr_t exp)
 158 {
 159       switch (ivl_expr_type(exp)) {
 160
 161           case IVL_EX_NUMBER:
 162           case IVL_EX_STRING:
 163             return 1;
 164
 165           default:
 166             return 0;
 167       }
 168 }
 169
 170 void save_expression_lookaside(unsigned addr, ivl_expr_t exp, unsigned wid)
 171 {
 172       unsigned idx;
 173       assert(addr >= 8);
 174       assert((addr+wid) <= MAX_VEC);
 175
 176         /* When saving an expression to the lookaside, also clear the
 177            signal saved in the lookaside for these bits. The reason is
 178            that an expression calculation will replace any signal
 179            bits. */
 180       for (idx = 0 ;  idx < wid ;  idx += 1)
 181             set_sig(addr+idx, 0, 0, 0);
 182
 183         /* Only certain types of expressions are savable. */
 184       if ( ! test_expression_savable(exp))
 185             return;
 186
 187       for (idx = 0 ;  idx < wid ;  idx += 1) {
 188             set_exp(addr+idx, exp, idx);
 189       }
 190
 191       if ((addr+wid) > lookaside_top)
 192             lookaside_top = addr+wid;
 193 }
 194
 195 static void clear_signal_lookaside_bit(unsigned idx, ivl_signal_t sig, unsigned sig_word)
 196 {
 197       if (allocation_map[idx].alloc > 0)
 198             return;
 199       if (allocation_map[idx].sig != sig)
 200             return;
 201       if (allocation_map[idx].sig_word != sig_word)
 202             return;
 203
 204       set_sig(idx, 0, 0, 0);
 205 }
 206
 207 void save_signal_lookaside(unsigned addr, ivl_signal_t sig, unsigned sig_word, unsigned wid)
 208 {
 209       unsigned idx;
 210         /* Don't bind any of the low bits to a signal. */
 211       if (addr < 8 && wid > 0)
 212             return;
 213
 214       assert((addr+wid) <= MAX_VEC);
 215
 216       for (idx = 8 ;  idx < addr ;  idx += 1)
 217             clear_signal_lookaside_bit(idx, sig, sig_word);
 218
 219       for (idx = 0 ;  idx < wid ;  idx += 1)
 220             set_sig(addr+idx, sig, sig_word, idx);
 221
 222       if ((addr+wid) > lookaside_top)
 223             lookaside_top = addr+wid;
 224
 225       for (idx = addr+wid ;  idx < lookaside_top ;  idx += 1)
 226             clear_signal_lookaside_bit(idx, sig, sig_word);
 227 }
 228
 229 static int compare_exp(ivl_expr_t l, ivl_expr_t r)
 230 {
 231       if (! (l && r))
 232             return 0;
 233       if (l == r)
 234             return 1;
 235
 236       if (ivl_expr_type(l) != ivl_expr_type(r))
 237             return 0;
 238
 239       switch (ivl_expr_type(l)) {
 240
 241           case IVL_EX_NUMBER:
 242             if (ivl_expr_width(l) != ivl_expr_width(r))
 243                   return 0;
 244             { const char*bitl = ivl_expr_bits(l);
 245               const char*bitr = ivl_expr_bits(r);
 246               unsigned idx;
 247               for (idx = 0 ;  idx < ivl_expr_width(l) ;  idx += 1) {
 248                     if (bitl[idx] != bitr[idx])
 249                           return 0;
 250               }
 251             }
 252             return 1;
 253
 254           case IVL_EX_SELECT:
 255             if (! compare_exp(ivl_expr_oper1(l), ivl_expr_oper1(r)))
 256                   return 0;
 257
 258             if (ivl_expr_oper2(l) == 0 && ivl_expr_oper1(r) == 0)
 259                   return 1;
 260
 261             if (! compare_exp(ivl_expr_oper2(l), ivl_expr_oper2(r)))
 262                   return 0;
 263
 264             return 1;
 265
 266           case IVL_EX_SIGNAL:
 267             if (ivl_expr_signal(l) != ivl_expr_signal(r))
 268                   return 0;
 269
 270             if (ivl_expr_width(l) != ivl_expr_width(r))
 271                   return 0;
 272
 273               /* Don't match array words. */
 274             if (ivl_expr_oper1(l) || ivl_expr_oper1(r))
 275                   return 0;
 276
 277             return 1;
 278
 279           default:
 280             break;
 281       }
 282
 283       return 0;
 284 }
 285
 286 static unsigned find_expression_lookaside(ivl_expr_t exp, unsigned wid)
 287 {
 288       unsigned top;
 289       unsigned idx, match;
 290       ivl_signal_t sig;
 291
 292       if (lookaside_top <= wid)
 293             return 0;
 294
 295       top = lookaside_top - wid + 1;
 296
 297         /* Look in the expression lookaside for this expression. */
 298       assert(exp);
 299       match = 0;
 300       for (idx = 8 ;  idx < lookaside_top ;  idx += 1) {
 301             if (! compare_exp(allocation_map[idx].exp, exp)) {
 302                   match = 0;
 303                   continue;
 304             }
 305
 306             if (allocation_map[idx].exp_bit != match) {
 307                   match = 0;
 308                   continue;
 309             }
 310
 311             match += 1;
 312             if (match == wid)
 313                   return idx-match+1;
 314       }
 315
 316         /* The general expression lookup failed. If this is an
 317            IVL_EX_SIGNAL, then look again in the variable lookaside
 318            (which is saved l-values) for the expression. */
 319       if (ivl_expr_type(exp) != IVL_EX_SIGNAL)
 320             return 0;
 321
 322       sig = ivl_expr_signal(exp);
 323
 324         /* Only reg signals (variables) will be in the signal
 325            lookaside, because only blocking assigned values are in the
 326            signal lookaside. */
 327       if (ivl_signal_type(sig) != IVL_SIT_REG)
 328             return 0;
 329
 330         /* Now look for signal value matches in the signal lookaside. */
 331       match = 0;
 332       for (idx = 8 ;  idx < lookaside_top ;  idx += 1) {
 333             if (sig != allocation_map[idx].sig) {
 334                   match = 0;
 335                   continue;
 336             }
 337
 338             if (allocation_map[idx].sig_bit != match) {
 339                   match = 0;
 340                   continue;
 341             }
 342
 343             match += 1;
 344             if (match == wid)
 345                   return idx-match+1;
 346
 347       }
 348
 349       return 0;
 350 }
 351
 352 /*
 353  * Look for the expression in the expression lookaside table. If it is
 354  * there, then allocate it and return the base. In this case the
 355  * caller will not need to evaluate the expression. If this function
 356  * returns 0, then the expression is not found and nothing is allocated.
 357  */
 358 unsigned allocate_vector_exp(ivl_expr_t exp, unsigned wid,
 359                              int exclusive_flag)
 360 {
 361       unsigned idx;
 362       unsigned la = find_expression_lookaside(exp, wid);
 363       if (la == 0)
 364             return 0;
 365
 366       if (exclusive_flag) {
 367               /* If the caller is requesting exclusive allocation of
 368                  the expression, then return not-found if a lookup
 369                  already matched the expression. */
 370             for (idx = 0 ;  idx < wid ;  idx += 1)
 371                   if (allocation_map[la+idx].alloc)
 372                         return 0;
 373       }
 374
 375       for (idx = 0 ;  idx < wid ;  idx += 1)
 376             allocation_map[la+idx].alloc += 1;
 377
 378       return la;
 379 }
 380
 381 /*
 382  * $Log: vector.c,v $
 383  * Revision 1.15  2007/04/01 05:26:17  steve
 384  *  Fix that save expression lookaside always clears cached variable values.
 385  *
 386  * Revision 1.14  2007/03/22 16:08:18  steve
 387  *  Spelling fixes from Larry
 388  *
 389  * Revision 1.13  2007/03/20 04:26:56  steve
 390  *  Clear lookaside even if source bit is a constant.
 391  *
 392  * Revision 1.12  2007/02/26 19:49:50  steve
 393  *  Spelling fixes (larry doolittle)
 394  *
 395  * Revision 1.11  2007/02/06 04:43:53  steve
 396  *  Expression lookaside cannot hold complex expressions
 397  *
 398  * Revision 1.10  2007/01/19 02:30:19  steve
 399  *  Fix bad lookaside references in vvp thread code generator.
 400  *
 401  * Revision 1.9  2007/01/18 00:59:48  steve
 402  *  Do not match array words in expression lookaside.
 403  *
 404  * Revision 1.8  2007/01/16 05:44:16  steve
 405  *  Major rework of array handling. Memories are replaced with the
 406  *  more general concept of arrays. The NetMemory and NetEMemory
 407  *  classes are removed from the ivl core program, and the IVL_LPM_RAM
 408  *  lpm type is removed from the ivl_target API.
 409  *
 410  * Revision 1.7  2005/09/17 01:01:00  steve
 411  *  More robust use of precalculated expressions, and
 412  *  Separate lookaside for written variables that can
 413  *  also be reused.
 414  *
 415  * Revision 1.6  2005/09/15 02:50:13  steve
 416  *  Preserve precalculated expressions when possible.
 417  *
 418  * Revision 1.5  2005/01/24 05:08:02  steve
 419  *  Part selects are done in the compiler, not here.
 420  *
 421  * Revision 1.4  2003/07/03 17:44:10  steve
 422  *  Wider thread vector limit.
 423  *
 424  * Revision 1.3  2003/06/17 19:17:42  steve
 425  *  Remove short int restrictions from vvp opcodes.
 426  *
 427  * Revision 1.2  2003/06/05 04:18:50  steve
 428  *  Better width testing for thread vector allocation.
 429  *
 430  * Revision 1.1  2002/09/27 16:33:34  steve
 431  *  Add thread expression lookaside map.
 432  *
 433  */
 434