sys/src/cmd/dtracy/cgen.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <dtracy.h>
   4 #include <bio.h>
   5 #include "dat.h"
   6 #include "fns.h"
   7
   8 u16int regsused = 1;
   9 u32int cbuf[256];
  10 int ncbuf;
  11 int labtab[256];
  12 int nlab;
  13
  14 static void
  15 emit(u32int x)
  16 {
  17         assert(ncbuf < nelem(cbuf));
  18         cbuf[ncbuf++] = x;
  19 }
  20
  21 static int
  22 regalloc(void)
  23 {
  24         u16int v;
  25         int n;
  26
  27         if(regsused == 0xffff){
  28                 error("out of registers");
  29                 return 0;
  30         }
  31         v = regsused + 1 & ~regsused;
  32         regsused ^= v;
  33         n = 0;
  34         if((u8int)v == 0) {v >>= 8; n += 8;}
  35         if((v & 0xf) == 0) {v >>= 4; n += 4;}
  36         if((v & 3) == 0) {v >>= 2; n += 2;}
  37         return n + (v >> 1);
  38 }
  39
  40 static void
  41 regfree(int n)
  42 {
  43         assert((regsused & 1<<n) != 0);
  44         assert(n != 0);
  45         regsused &= ~(1<<n);
  46 }
  47
  48 static int
  49 popcount(u64int s)
  50 {
  51         s = (s & 0x5555555555555555ULL) + (s >> 1 & 0x5555555555555555ULL);
  52         s = (s & 0x3333333333333333ULL) + (s >> 2 & 0x3333333333333333ULL);
  53         s = (s & 0x0F0F0F0F0F0F0F0FULL) + (s >> 4 & 0x0F0F0F0F0F0F0F0FULL);
  54         s = (s & 0x00FF00FF00FF00FFULL) + (s >> 8 & 0x00FF00FF00FF00FFULL);
  55         s = (s & 0x0000FFFF0000FFFFULL) + (s >> 16 & 0x0000FFFF0000FFFFULL);
  56         return (u32int)s + (u32int)(s >> 32);
  57 }
  58
  59 static int
  60 constenc(s64int val)
  61 {
  62         int i, r;
  63         s64int x;
  64
  65         r = 0;
  66         do{
  67                 i = popcount(val ^ val - 1) - 1;
  68                 x = val << 54 - i >> 54;
  69                 if(r == 0){
  70                         r = regalloc();
  71                         emit(DTE_LDI << 24 | (x & 0x3ff) << 14 | i << 8 | r);
  72                 }else
  73                         emit(DTE_XORI << 24 | (x & 0x3ff) << 14 | i << 8 | r);
  74                 val ^= x << i;
  75         }while(val != 0);
  76         return r;
  77 }
  78
  79 static int egen(Node *);
  80
  81 static void
  82 condgen(Node *n, int invert, int truelab)
  83 {
  84         int r1, r2, l1, op;
  85
  86         if(n->type != OBIN) goto other;
  87         switch(n->op){
  88         case OPEQ: op = DTE_SEQ; goto cmp;
  89         case OPNE: op = DTE_SNE; goto cmp;
  90         case OPLT: op = DTE_SLT; goto cmp;
  91         case OPLE: op = DTE_SLE;
  92         cmp:
  93                 r1 = egen(n->n1);
  94                 r2 = egen(n->n2);
  95                 if(invert)
  96                         emit(DTE(op ^ 1, r2, r1, truelab));
  97                 else
  98                         emit(DTE(op, r1, r2, truelab));
  99                 regfree(r1);
 100                 regfree(r2);
 101                 break;
 102         case OPLOR:
 103         case OPLAND:
 104                 if(invert ^ n->op == OPLOR){
 105                         condgen(n->n1, invert, truelab);
 106                         condgen(n->n2, invert, truelab);
 107                 }else{
 108                         l1 = nlab++;
 109                         condgen(n->n1, !invert, l1);
 110                         condgen(n->n2, invert, truelab);
 111                         labtab[l1] = ncbuf;
 112                 }
 113                 break;
 114         default:
 115         other:
 116                 r1 = egen(n);
 117                 emit(DTE(DTE_BNE ^ invert, r1, 0, truelab));
 118                 regfree(r1);
 119                 break;
 120         }
 121 }
 122
 123 static int
 124 condvgen(Node *n, int invert)
 125 {
 126         int r, l1, l2, op;
 127
 128         if(n->type == OLNOT)
 129                 return condvgen(n->n1, !invert);
 130         if(n->type != OBIN) goto other;
 131         switch(n->op){
 132         case OPEQ: op = DTE_SEQ; goto cmp;
 133         case OPNE: op = DTE_SNE; goto cmp;
 134         case OPLT: op = DTE_SLT; goto cmp;
 135         case OPLE: op = DTE_SLE;
 136         cmp:
 137                 if(invert)
 138                         return egen(node(OBIN, op ^ 1, n->n2, n->n1));
 139                 return egen(n);
 140         case OPLOR:
 141         case OPLAND:
 142                 if(invert ^ n->op == OPLOR){
 143                         l1 = nlab++;
 144                         l2 = nlab++;
 145                         condgen(n->n1, invert, l1);
 146                         r = condvgen(n->n2, invert);
 147                         emit(DTE(DTE_BEQ, 0, 0, l2));
 148                         labtab[l1] = ncbuf;
 149                         emit(DTE(DTE_LDI, 0, 1<<6, r));
 150                         labtab[l2] = ncbuf;
 151                         return r;
 152                 }else{
 153                         l1 = nlab++;
 154                         l2 = nlab++;
 155                         condgen(n->n1, invert, l1);
 156                         r = condvgen(n->n2, invert);
 157                         emit(DTE(DTE_BEQ, 0, 0, l2));
 158                         labtab[l1] = ncbuf;
 159                         emit(DTE(DTE_LDI, 0, 0<<6, r));
 160                         labtab[l2] = ncbuf;
 161                         return r;
 162                 }
 163         default:
 164         other:
 165                 r = egen(n);
 166                 emit(DTE(DTE_SNE ^ invert, r, 0, r));
 167                 return r;
 168         }
 169 }
 170
 171 static int
 172 egen(Node *n)
 173 {
 174         int r1, r2, rt, l1, l2, op;
 175
 176         switch(/*nodetype*/n->type){
 177         case ONUM:
 178                 return constenc(n->num);
 179         case OSYM:
 180                 switch(n->sym->type){
 181                 case SYMVAR:
 182                         rt = regalloc();
 183                         emit(DTE(DTE_LDV, n->sym->idx, rt, 0));
 184                         return rt;
 185                 default: sysfatal("egen: unknown symbol type %d", n->sym->type); return 0;
 186                 }
 187         case OBIN:
 188                 switch(/*oper*/n->op){
 189                 case OPLAND:
 190                 case OPLOR:
 191                         return condvgen(n, 0);
 192                 case OPADD: op = DTE_ADD; break;
 193                 case OPSUB: op = DTE_SUB; break;
 194                 case OPMUL: op = DTE_MUL; break;
 195                 case OPDIV: op = n->typ->sign ? DTE_SDIV : DTE_UDIV; break;
 196                 case OPMOD: op = n->typ->sign ? DTE_SMOD : DTE_UMOD; break;
 197                 case OPAND: op = DTE_AND; break;
 198                 case OPOR: op = DTE_OR; break;
 199                 case OPXOR: op = DTE_XOR; break;
 200                 case OPLSH: op = DTE_LSL; break;
 201                 case OPRSH: op = n->typ->sign ? DTE_ASR : DTE_LSR; break;
 202                 case OPEQ: op = DTE_SEQ; break;
 203                 case OPNE: op = DTE_SNE; break;
 204                 case OPLT: op = DTE_SLT; break;
 205                 case OPLE: op = DTE_SLE; break;
 206                 case OPXNOR: op = DTE_XNOR; break;
 207                 default: sysfatal("egen: unknown op %d", n->op); return 0;
 208                 }
 209                 r1 = egen(n->n1);
 210                 r2 = egen(n->n2);
 211                 regfree(r1);
 212                 regfree(r2);
 213                 rt = regalloc();
 214                 emit(DTE(op, r1, r2, rt));
 215                 return rt;
 216         case OTERN:
 217                 l1 = nlab++;
 218                 l2 = nlab++;
 219                 condgen(n->n1, 1, l1);
 220                 r1 = egen(n->n2);
 221                 emit(DTE(DTE_BEQ, 0, 0, l2));
 222                 labtab[l1] = ncbuf;
 223                 r2 = egen(n->n3);
 224                 if(r1 != r2)
 225                         emit(DTE(DTE_OR, 0, r2, r1));
 226                 labtab[l2] = ncbuf;
 227                 return r1;
 228         case OLNOT:
 229                 return condvgen(n, 0);
 230         case OCAST:
 231                 switch(n->typ->type){
 232                 case TYPINT:
 233                         r1 = egen(n->n1);
 234                         emit(DTE(n->typ->sign ? DTE_SXT : DTE_ZXT, r1, n->typ->size * 8, r1));
 235                         return r1;
 236                 case TYPSTRING:
 237                         return egen(n->n1);
 238                 default:
 239                         sysfatal("egen: don't know how to cast %τ to %τ", n->n1->typ, n->typ);
 240                 }
 241         case ORECORD:
 242         case OSTR:
 243         default: sysfatal("egen: unknown type %α", n->type); return 0;
 244         }
 245 }
 246
 247 DTExpr *
 248 codegen(Node *n)
 249 {
 250         int r, i, t;
 251         DTExpr *ep;
 252
 253         regsused = 1;
 254         ncbuf = 0;
 255         nlab = 0;
 256         r = egen(n);
 257         emit(DTE(DTE_RET, r, 0, 0));
 258
 259         for(i = 0; i < ncbuf; i++)
 260                 if((cbuf[i] >> 24 & 0xf0) == 0x30){
 261                         t = labtab[cbuf[i] & 0xff];
 262                         assert((uint)(t - i - 1) < 0x100);
 263                         cbuf[i] = cbuf[i] & 0xffffff00 | t - i - 1;
 264                 }
 265
 266         ep = emalloc(sizeof(DTExpr) + ncbuf * sizeof(u32int));
 267         ep->n = ncbuf;
 268         ep->b = (void *)(ep + 1);
 269         memcpy(ep->b, cbuf, ncbuf * sizeof(u32int));
 270         return ep;
 271 }
 272
 273 Node *
 274 tracegen(Node *n, DTActGr *g, int *recoff)
 275 {
 276         switch(/*nodetype*/n->type){
 277         case OSYM:
 278         case ONUM:
 279         case OSTR:
 280                 break;
 281         case OBIN:
 282                 n->n1 = tracegen(n->n1, g, recoff);
 283                 n->n2 = tracegen(n->n2, g, recoff);
 284                 break;
 285         case OLNOT:
 286                 n->n1 = tracegen(n->n1, g, recoff);
 287                 break;
 288         case OTERN:
 289                 n->n1 = tracegen(n->n1, g, recoff);
 290                 n->n2 = tracegen(n->n2, g, recoff);
 291                 n->n3 = tracegen(n->n3, g, recoff);
 292                 break;
 293         case OCAST:
 294                 n->n1 = tracegen(n->n1, g, recoff);
 295                 break;
 296         case ORECORD:
 297                 switch(n->typ->type){
 298                 case TYPINT:
 299                         actgradd(g, (DTAct){ACTTRACE, codegen(n->n1), n->typ->size, noagg});
 300                         break;
 301                 case TYPSTRING:
 302                         actgradd(g, (DTAct){ACTTRACESTR, codegen(n->n1), n->typ->size, noagg});
 303                         break;
 304                 default:
 305                         sysfatal("tracegen: don't know how to record %τ", n->typ);
 306                 }
 307                 n->num = *recoff;
 308                 *recoff += n->typ->size;
 309                 return n;
 310         default: sysfatal("tracegen: unknown type %α", n->type); return nil;
 311         }
 312         return n;
 313 }