liveness.c

   1 /*
   2  * Copyright (C) 2012, 2013, 2014
   3  *     Wolfgang Bumiller
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a copy of
   6  * this software and associated documentation files (the "Software"), to deal in
   7  * the Software without restriction, including without limitation the rights to
   8  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
   9  * of the Software, and to permit persons to whom the Software is furnished to do
  10  * so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in all
  13  * copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21  * SOFTWARE.
  22  */
  23
  24 #include <stdlib.h>
  25
  26 #include "gmqcc.h"
  27 #include "liveness.h"
  28
  29 ir_bitlist_t *ir_bitlist_new() {
  30     ir_bitlist_t *list = (ir_bitlist_t*)mem_a(sizeof(ir_bitlist_t));
  31     list->bits = NULL;
  32     return list;
  33 }
  34
  35 void ir_bitlist_delete(ir_bitlist_t *self) {
  36     if (self->bits)
  37         vec_free(self->bits);
  38     mem_d(self);
  39 }
  40
  41 static GMQCC_INLINE void ir_bitlist_allocindex(ir_bitlist_t *self, size_t index) {
  42     size_t size  = vec_size(self->bits);
  43     while (size++ <= index)
  44         vec_push(self->bits, 0);
  45 }
  46
  47 void ir_bitlist_setrange(ir_bitlist_t *self, size_t from, size_t to) {
  48     size_t index_from, bit_from, index_to, bit_to;
  49     GMQCC_BL_TYPE mask;
  50
  51     if (from > to) {
  52         con_err("ir_bitlist_setrange: bad bits\n");
  53         abort();
  54     }
  55
  56     ++to;
  57     index_from = from / GMQCC_BL_BITS;
  58     bit_from   = from % GMQCC_BL_BITS;
  59     index_to   = to   / GMQCC_BL_BITS;
  60     bit_to     = to   % GMQCC_BL_BITS;
  61
  62     ir_bitlist_allocindex(self, index_to);
  63
  64     mask = GMQCC_BL_FULL;
  65
  66     if (index_from == index_to) {
  67         mask <<= bit_from;
  68         mask <<= GMQCC_BL_BITS - bit_to;
  69         mask >>= GMQCC_BL_BITS - bit_to;
  70         self->bits[index_from] |= mask;
  71         return;
  72     }
  73
  74     /* first chunk: */
  75     self->bits[index_from] |= mask << bit_from;
  76     /* filled with all ones */
  77     for (++index_from; index_from != index_to; ++index_from)
  78         self->bits[index_from] |= mask;
  79     /* last chunk */
  80     mask <<= GMQCC_BL_BITS - bit_to;
  81     mask >>= GMQCC_BL_BITS - bit_to;
  82     self->bits[index_to] |= mask;
  83 }
  84
  85 static void ir_bitlist_dump(const ir_bitlist_t *self,
  86                             int (*oprintf)(const char*, ...))
  87 {
  88     size_t i;
  89     size_t size = vec_size(self->bits);
  90     if (!size)
  91         oprintf("<empty>");
  92     for (i = 0; i != size; ++i) {
  93         size_t b;
  94         for (b = 0; b != GMQCC_BL_BITS; ++b)
  95             oprintf( (self->bits[i] & (1UL<<b)) ? "1" : "0" );
  96     }
  97     oprintf("\n");
  98 }
  99
 100 ir_lifemask_t *ir_lifemask_new(size_t size) {
 101     ir_lifemask_t *self;
 102     self        = (ir_lifemask_t*)mem_a(sizeof(*self));
 103     self->alive = ir_bitlist_new();
 104     self->dies  = ir_bitlist_new();
 105     self->used  = false;
 106     ir_bitlist_allocindex(self->alive, size / GMQCC_BL_BITS);
 107     ir_bitlist_allocindex(self->dies,  size / GMQCC_BL_BITS);
 108     return self;
 109 }
 110
 111 void ir_lifemask_delete(ir_lifemask_t *self) {
 112     ir_bitlist_delete(self->alive);
 113     ir_bitlist_delete(self->dies);
 114     /*if (self->mask)
 115         ir_bitlist_delete(self->mask);*/
 116     mem_d(self);
 117 }
 118
 119 void ir_lifemask_merge(ir_lifemask_t *self, const ir_lifemask_t *other) {
 120     size_t i;
 121     size_t other_alive_size = vec_size(other->alive->bits);
 122     if (!other_alive_size)
 123         return;
 124
 125     /*
 126     ir_bitlist_allocindex(self->alive, other_alive_size-1);
 127     ir_bitlist_allocindex(self->dies,  other_alive_size-1);
 128     */
 129     /*if (self->mask)
 130         ir_bitlist_allocindex(self->mask,  other_alive_size-1);*/
 131
 132     for (i = 0; i != other_alive_size; ++i) {
 133         self->alive->bits[i] |= other->alive->bits[i];
 134         self->dies->bits[i]  &= ~self->alive->bits[i];
 135         self->dies->bits[i]  |= ~other->alive->bits[i] & other->dies->bits[i];
 136
 137         /*if (self->mask)
 138             self->mask->bits[i] = self->alive->bits[i] & ~self->dies->bits[i];*/
 139         self->used = self->alive->bits[i] || self->used;
 140     }
 141 }
 142
 143 /*
 144 void ir_lifemask_setmask(ir_lifemask_t *self) {
 145     size_t i;
 146     size_t size;
 147
 148     if (!self->mask)
 149         self->mask = ir_bitlist_new();
 150
 151     size = vec_size(self->alive->bits);
 152     if (!size)
 153         return;
 154
 155     ir_bitlist_allocindex(self->mask, size-1);
 156     for (i = 0; i != size; ++i)
 157         self->mask->bits[i] = self->alive->bits[i] & ~self->dies->bits[i];
 158 }
 159 */
 160
 161 bool ir_lifemask_overlaps(const ir_lifemask_t *a, const ir_lifemask_t *b) {
 162     size_t i;
 163     size_t size   = vec_size(a->alive->bits),
 164            size_b = vec_size(b->alive->bits);
 165     if (size > size_b)
 166         size = size_b;
 167     for (i = 0; i != size; ++i) {
 168         GMQCC_BL_TYPE mask_a = a->alive->bits[i] & ~a->dies->bits[i];
 169         GMQCC_BL_TYPE mask_b = b->alive->bits[i] & ~b->dies->bits[i];
 170         if (mask_a & mask_b)
 171             return true;
 172     }
 173     return false;
 174 }
 175
 176 void ir_lifemask_dump(const ir_lifemask_t *self, const char *ind,
 177                       int (*oprintf)(const char*, ...))
 178 {
 179     oprintf("{\n%s  ", ind);
 180     ir_bitlist_dump(self->alive, oprintf);
 181     oprintf("%s  ", ind);
 182     ir_bitlist_dump(self->dies, oprintf);
 183     /*oprintf("%s  ", ind);
 184     ir_bitlist_dump(self->mask, oprintf);*/
 185     oprintf("%s}\n", ind);
 186 }
 187
 188 #ifdef LIVETEST
 189 #include <stdio.h>
 190 void test_liveness() {
 191     con_init();
 192     ir_bitlist_t *bl = ir_bitlist_new();
 193     ir_bitlist_dump(bl);
 194     ir_bitlist_setbit(bl, 1);
 195     ir_bitlist_dump(bl);
 196     ir_bitlist_setbit(bl, 2);
 197     ir_bitlist_dump(bl);
 198     ir_bitlist_setrange(bl, 4, 6);
 199     ir_bitlist_dump(bl);
 200     ir_bitlist_setrange(bl, 8, 9);
 201     ir_bitlist_dump(bl);
 202     ir_bitlist_setrange(bl, 15, 17);
 203     ir_bitlist_dump(bl);
 204     ir_bitlist_delete(bl);
 205
 206     ir_lifemask_t ma, mb;
 207     ir_lifemask_init(&ma);
 208     ir_lifemask_init(&mb);
 209
 210     ir_bitlist_setrange(ma.alive, 4, 6);
 211     ir_bitlist_setbit(ma.dies,  4);
 212     ir_lifemask_dump(&ma);
 213
 214     ir_bitlist_setrange(mb.alive, 6, 8);
 215     ir_bitlist_setbit(mb.dies,  6);
 216     ir_lifemask_dump(&mb);
 217     con_out(ir_lifemask_overlaps(&ma, &mb) ? "WRONG OVERLAP\n" : "Ok\n");
 218
 219     ir_bitlist_setrange(mb.alive, 9, 12);
 220     ir_bitlist_setbit(mb.dies,  9);
 221     ir_lifemask_dump(&mb);
 222     con_out(ir_lifemask_overlaps(&ma, &mb) ? "WRONG OVERLAP\n" : "Ok\n");
 223
 224     ir_bitlist_setrange(mb.alive, 5, 7);
 225     ir_bitlist_unsetbit(mb.dies,  6);
 226     ir_bitlist_setbit(mb.dies,  5);
 227     ir_lifemask_dump(&mb);
 228     con_out(ir_lifemask_overlaps(&ma, &mb) ? "overlap\n" : "WRONG ! OVERLAPPING\n");
 229
 230     ir_lifemask_clear(&ma);
 231     ir_lifemask_clear(&mb);
 232 }
 233
 234 int main() {
 235     test_liveness();
 236     return 0;
 237 }
 238 #endif