sparse-llvm.c

   1 /*
   2  * Example usage:
   3  *      ./sparse-llvm hello.c | llc | as -o hello.o
   4  */
   5
   6 #include <llvm-c/Core.h>
   7 #include <llvm-c/BitWriter.h>
   8
   9 #include <stdio.h>
  10 #include <unistd.h>
  11 #include <assert.h>
  12
  13 #include "symbol.h"
  14 #include "expression.h"
  15 #include "linearize.h"
  16 #include "flow.h"
  17
  18 struct function {
  19         LLVMBuilderRef                  builder;
  20         LLVMTypeRef                     type;
  21         LLVMValueRef                    fn;
  22 };
  23
  24 static LLVMTypeRef symbol_type(struct symbol *sym)
  25 {
  26         LLVMTypeRef ret = NULL;
  27
  28         switch (sym->bit_size) {
  29         case -1:
  30                 ret = LLVMVoidType();
  31                 break;
  32         case 8:
  33                 ret = LLVMInt8Type();
  34                 break;
  35         case 16:
  36                 ret = LLVMInt16Type();
  37                 break;
  38         case 32:
  39                 ret = LLVMInt32Type();
  40                 break;
  41         case 64:
  42                 ret = LLVMInt64Type();
  43                 break;
  44         default:
  45                 die("invalid bit size %d for type %d", sym->bit_size, sym->type);
  46                 break;
  47         };
  48
  49         return ret;
  50 }
  51
  52 static LLVMLinkage data_linkage(struct symbol *sym)
  53 {
  54         if (sym->ctype.modifiers & MOD_STATIC)
  55                 return LLVMPrivateLinkage;
  56
  57         return LLVMExternalLinkage;
  58 }
  59
  60 static LLVMLinkage function_linkage(struct symbol *sym)
  61 {
  62         if (sym->ctype.modifiers & MOD_STATIC)
  63                 return LLVMInternalLinkage;
  64
  65         return LLVMExternalLinkage;
  66 }
  67
  68 #define MAX_PSEUDO_NAME 64
  69
  70 static void pseudo_name(pseudo_t pseudo, char *buf)
  71 {
  72         switch (pseudo->type) {
  73         case PSEUDO_REG:
  74                 snprintf(buf, MAX_PSEUDO_NAME, "R%d", pseudo->nr);
  75                 break;
  76         case PSEUDO_SYM:
  77                 assert(0);
  78                 break;
  79         case PSEUDO_VAL:
  80                 assert(0);
  81                 break;
  82         case PSEUDO_ARG: {
  83                 assert(0);
  84                 break;
  85         }
  86         case PSEUDO_PHI:
  87                 snprintf(buf, MAX_PSEUDO_NAME, "PHI%d", pseudo->nr);
  88                 break;
  89         default:
  90                 assert(0);
  91         }
  92 }
  93
  94 static LLVMValueRef pseudo_to_value(struct function *fn, pseudo_t pseudo)
  95 {
  96         LLVMValueRef result;
  97
  98         switch (pseudo->type) {
  99         case PSEUDO_REG:
 100                 result = pseudo->priv;
 101                 break;
 102         case PSEUDO_SYM:
 103                 assert(0);
 104                 break;
 105         case PSEUDO_VAL:
 106                 result = LLVMConstInt(LLVMGetReturnType(fn->type), pseudo->value, 1);
 107                 break;
 108         case PSEUDO_ARG: {
 109                 result = LLVMGetParam(fn->fn, pseudo->nr - 1);
 110                 break;
 111         }
 112         case PSEUDO_PHI:
 113                 result = pseudo->priv;
 114                 break;
 115         case PSEUDO_VOID:
 116                 result = NULL;
 117                 break;
 118         default:
 119                 assert(0);
 120         }
 121
 122         return result;
 123 }
 124
 125 static void output_op_binary(struct function *fn, struct instruction *insn)
 126 {
 127         LLVMValueRef lhs, rhs, target;
 128         char target_name[64];
 129
 130         lhs = pseudo_to_value(fn, insn->src1);
 131
 132         rhs = pseudo_to_value(fn, insn->src2);
 133
 134         pseudo_name(insn->target, target_name);
 135
 136         switch (insn->opcode) {
 137         /* Binary */
 138         case OP_ADD:
 139                 target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name);
 140                 break;
 141         case OP_SUB:
 142                 target = LLVMBuildSub(fn->builder, lhs, rhs, target_name);
 143                 break;
 144         case OP_MULU:
 145                 target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
 146                 break;
 147         case OP_MULS:
 148                 target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
 149                 break;
 150         case OP_DIVU:
 151                 target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name);
 152                 break;
 153         case OP_DIVS:
 154                 target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name);
 155                 break;
 156         case OP_MODU:
 157                 target = LLVMBuildURem(fn->builder, lhs, rhs, target_name);
 158                 break;
 159         case OP_MODS:
 160                 target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name);
 161                 break;
 162         case OP_SHL:
 163                 target = LLVMBuildShl(fn->builder, lhs, rhs, target_name);
 164                 break;
 165         case OP_LSR:
 166                 target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name);
 167                 break;
 168         case OP_ASR:
 169                 target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name);
 170                 break;
 171
 172         /* Logical */
 173         case OP_AND:
 174                 target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name);
 175                 break;
 176         case OP_OR:
 177                 target = LLVMBuildOr(fn->builder, lhs, rhs, target_name);
 178                 break;
 179         case OP_XOR:
 180                 target = LLVMBuildXor(fn->builder, lhs, rhs, target_name);
 181                 break;
 182         case OP_AND_BOOL:
 183                 assert(0);
 184                 break;
 185         case OP_OR_BOOL:
 186                 assert(0);
 187                 break;
 188
 189         /* Binary comparison */
 190         case OP_SET_EQ:
 191                 target = LLVMBuildICmp(fn->builder, LLVMIntEQ, lhs, rhs, target_name);
 192                 break;
 193         case OP_SET_NE:
 194                 target = LLVMBuildICmp(fn->builder, LLVMIntNE, lhs, rhs, target_name);
 195                 break;
 196         case OP_SET_LE:
 197                 assert(0);
 198                 break;
 199         case OP_SET_GE:
 200                 assert(0);
 201                 break;
 202         case OP_SET_LT:
 203                 target = LLVMBuildICmp(fn->builder, LLVMIntSLT, lhs, rhs, target_name);
 204                 break;
 205         case OP_SET_GT:
 206                 target = LLVMBuildICmp(fn->builder, LLVMIntSGT, lhs, rhs, target_name);
 207                 break;
 208         case OP_SET_B:
 209                 assert(0);
 210                 break;
 211         case OP_SET_A:
 212                 assert(0);
 213                 break;
 214         case OP_SET_BE:
 215                 assert(0);
 216                 break;
 217         case OP_SET_AE:
 218                 assert(0);
 219                 break;
 220         default:
 221                 assert(0);
 222                 break;
 223         }
 224
 225         insn->target->priv = target;
 226 }
 227
 228 static void output_op_ret(struct function *fn, struct instruction *insn)
 229 {
 230         pseudo_t pseudo = insn->src;
 231
 232         if (pseudo && pseudo != VOID) {
 233                 LLVMValueRef result = pseudo_to_value(fn, pseudo);
 234
 235                 LLVMBuildRet(fn->builder, result);
 236         } else
 237                 LLVMBuildRetVoid(fn->builder);
 238 }
 239
 240 static void output_op_br(struct function *fn, struct instruction *br)
 241 {
 242         if (br->cond) {
 243                 LLVMValueRef cond = pseudo_to_value(fn, br->cond);
 244
 245                 LLVMBuildCondBr(fn->builder, cond,
 246                                 br->bb_true->priv,
 247                                 br->bb_false->priv);
 248         } else
 249                 LLVMBuildBr(fn->builder,
 250                             br->bb_true ? br->bb_true->priv :
 251                             br->bb_false->priv);
 252 }
 253
 254 static void output_op_sel(struct function *fn, struct instruction *insn)
 255 {
 256         LLVMValueRef target, src1, src2, src3;
 257
 258         src1 = pseudo_to_value(fn, insn->src1);
 259         src2 = pseudo_to_value(fn, insn->src2);
 260         src3 = pseudo_to_value(fn, insn->src3);
 261
 262         target = LLVMBuildSelect(fn->builder, src1, src2, src3, "select");
 263
 264         insn->target->priv = target;
 265 }
 266
 267 static void output_op_switch(struct function *fn, struct instruction *insn)
 268 {
 269         LLVMValueRef sw_val, target;
 270         struct basic_block *def = NULL;
 271         struct multijmp *jmp;
 272         int n_jmp = 0;
 273
 274         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 275                 if (jmp->begin == jmp->end) {           /* case N */
 276                         n_jmp++;
 277                 } else if (jmp->begin < jmp->end) {     /* case M..N */
 278                         /* FIXME */
 279                 } else                                  /* default case */
 280                         def = jmp->target;
 281         } END_FOR_EACH_PTR(jmp);
 282
 283         sw_val = pseudo_to_value(fn, insn->target);
 284         target = LLVMBuildSwitch(fn->builder, sw_val,
 285                                  def ? def->priv : NULL, n_jmp);
 286
 287         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 288                 if (jmp->begin == jmp->end) {           /* case N */
 289                         LLVMAddCase(target,
 290                                 LLVMConstInt(LLVMInt32Type(), jmp->begin, 0),
 291                                 jmp->target->priv);
 292                 } else if (jmp->begin < jmp->end) {     /* case M..N */
 293                         /* FIXME */
 294                 }
 295         } END_FOR_EACH_PTR(jmp);
 296
 297         insn->target->priv = target;
 298 }
 299
 300 static void output_insn(struct function *fn, struct instruction *insn)
 301 {
 302         switch (insn->opcode) {
 303         case OP_RET:
 304                 output_op_ret(fn, insn);
 305                 break;
 306         case OP_BR:
 307                 output_op_br(fn, insn);
 308                 break;
 309         case OP_SYMADDR:
 310                 assert(0);
 311                 break;
 312         case OP_SETVAL:
 313                 assert(0);
 314                 break;
 315         case OP_SWITCH:
 316                 output_op_switch(fn, insn);
 317                 break;
 318         case OP_COMPUTEDGOTO:
 319                 assert(0);
 320                 break;
 321         case OP_PHISOURCE: {
 322                 LLVMValueRef src, target;
 323                 char target_name[64];
 324
 325                 pseudo_name(insn->target, target_name);
 326                 src = pseudo_to_value(fn, insn->phi_src);
 327
 328                 target = LLVMBuildAdd(fn->builder, src,
 329                         LLVMConstInt(LLVMInt32Type(), 0, 0), target_name);
 330
 331                 insn->target->priv = target;
 332                 break;
 333         }
 334         case OP_PHI: {
 335                 pseudo_t phi;
 336                 LLVMValueRef target;
 337
 338                 target = LLVMBuildPhi(fn->builder, symbol_type(insn->type),
 339                                         "phi");
 340                 int pll = 0;
 341                 FOR_EACH_PTR(insn->phi_list, phi) {
 342                         if (pseudo_to_value(fn, phi))   /* skip VOID */
 343                                 pll++;
 344                 } END_FOR_EACH_PTR(phi);
 345
 346                 LLVMValueRef *phi_vals = calloc(pll, sizeof(LLVMValueRef));
 347                 LLVMBasicBlockRef *phi_blks = calloc(pll, sizeof(LLVMBasicBlockRef));
 348
 349                 int idx = 0;
 350                 FOR_EACH_PTR(insn->phi_list, phi) {
 351                         LLVMValueRef v;
 352
 353                         v = pseudo_to_value(fn, phi);
 354                         if (v) {                        /* skip VOID */
 355                                 phi_vals[idx] = v;
 356                                 phi_blks[idx] = phi->def->bb->priv;
 357                                 idx++;
 358                         }
 359                 } END_FOR_EACH_PTR(phi);
 360
 361                 LLVMAddIncoming(target, phi_vals, phi_blks, pll);
 362
 363                 insn->target->priv = target;
 364                 break;
 365         }
 366         case OP_LOAD: case OP_LNOP:
 367                 assert(0);
 368                 break;
 369         case OP_STORE: case OP_SNOP:
 370                 assert(0);
 371                 break;
 372         case OP_INLINED_CALL:
 373         case OP_CALL:
 374                 assert(0);
 375                 break;
 376         case OP_CAST: {
 377                 LLVMValueRef src, target;
 378                 char target_name[64];
 379
 380                 src = insn->src->priv;
 381
 382                 pseudo_name(insn->target, target_name);
 383
 384                 target = LLVMBuildIntCast(fn->builder, src, symbol_type(insn->type), target_name);
 385
 386                 insn->target->priv = target;
 387                 break;
 388         } case OP_SCAST:
 389                 assert(0);
 390                 break;
 391         case OP_FPCAST:
 392                 assert(0);
 393                 break;
 394         case OP_PTRCAST:
 395                 assert(0);
 396                 break;
 397         case OP_BINARY ... OP_BINARY_END:
 398         case OP_BINCMP ... OP_BINCMP_END:
 399                 output_op_binary(fn, insn);
 400                 break;
 401         case OP_SEL:
 402                 output_op_sel(fn, insn);
 403                 break;
 404         case OP_SLICE:
 405                 assert(0);
 406                 break;
 407         case OP_NOT: case OP_NEG:
 408                 assert(0);
 409                 break;
 410         case OP_CONTEXT:
 411                 assert(0);
 412                 break;
 413         case OP_RANGE:
 414                 assert(0);
 415                 break;
 416         case OP_NOP:
 417                 assert(0);
 418                 break;
 419         case OP_DEATHNOTE:
 420                 assert(0);
 421                 break;
 422         case OP_ASM:
 423                 assert(0);
 424                 break;
 425         case OP_COPY: {
 426                 LLVMValueRef src, target;
 427                 char target_name[64];
 428
 429                 pseudo_name(insn->target, target_name);
 430                 src = pseudo_to_value(fn, insn->src);
 431
 432                 target = LLVMBuildAdd(fn->builder, src,
 433                         LLVMConstInt(LLVMInt32Type(), 0, 0), target_name);
 434
 435                 insn->target->priv = target;
 436                 break;
 437         }
 438         default:
 439                 break;
 440         }
 441 }
 442
 443 static void output_bb(struct function *fn, struct basic_block *bb, unsigned long generation)
 444 {
 445         struct instruction *insn;
 446
 447         bb->generation = generation;
 448
 449         FOR_EACH_PTR(bb->insns, insn) {
 450                 if (!insn->bb)
 451                         continue;
 452
 453                 output_insn(fn, insn);
 454         }
 455         END_FOR_EACH_PTR(insn);
 456 }
 457
 458 #define MAX_ARGS        64
 459
 460 static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
 461 {
 462         unsigned long generation = ++bb_generation;
 463         struct symbol *sym = ep->name;
 464         struct symbol *base_type = sym->ctype.base_type;
 465         struct symbol *ret_type = sym->ctype.base_type->ctype.base_type;
 466         LLVMTypeRef arg_types[MAX_ARGS];
 467         LLVMTypeRef return_type;
 468         struct function function;
 469         struct basic_block *bb;
 470         struct symbol *arg;
 471         const char *name;
 472         int nr_args = 0;
 473
 474         FOR_EACH_PTR(base_type->arguments, arg) {
 475                 struct symbol *arg_base_type = arg->ctype.base_type;
 476
 477                 arg_types[nr_args++] = symbol_type(arg_base_type);
 478         } END_FOR_EACH_PTR(arg);
 479
 480         name = show_ident(sym->ident);
 481
 482         return_type = symbol_type(ret_type);
 483
 484         function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0);
 485
 486         function.fn = LLVMAddFunction(module, name, function.type);
 487         LLVMSetFunctionCallConv(function.fn, LLVMCCallConv);
 488
 489         LLVMSetLinkage(function.fn, function_linkage(sym));
 490
 491 #if 0
 492         unssa(ep);
 493 #endif
 494
 495         function.builder = LLVMCreateBuilder();
 496
 497         static int nr_bb;
 498
 499         FOR_EACH_PTR(ep->bbs, bb) {
 500                 if (bb->generation == generation)
 501                         continue;
 502
 503                 LLVMBasicBlockRef bbr;
 504                 char bbname[32];
 505
 506                 sprintf(bbname, "L%d", nr_bb++);
 507                 bbr = LLVMAppendBasicBlock(function.fn, bbname);
 508
 509                 bb->priv = bbr;
 510         }
 511         END_FOR_EACH_PTR(bb);
 512
 513         FOR_EACH_PTR(ep->bbs, bb) {
 514                 if (bb->generation == generation)
 515                         continue;
 516
 517                 LLVMPositionBuilderAtEnd(function.builder, bb->priv);
 518
 519                 output_bb(&function, bb, generation);
 520         }
 521         END_FOR_EACH_PTR(bb);
 522 }
 523
 524 static int output_data(LLVMModuleRef module, struct symbol *sym)
 525 {
 526         struct expression *initializer = sym->initializer;
 527         unsigned long long initial_value = 0;
 528         LLVMValueRef data;
 529         const char *name;
 530
 531         if (initializer) {
 532                 if (initializer->type == EXPR_VALUE)
 533                         initial_value = initializer->value;
 534                 else
 535                         assert(0);
 536         }
 537
 538         name = show_ident(sym->ident);
 539
 540         data = LLVMAddGlobal(module, symbol_type(sym->ctype.base_type), name);
 541
 542         LLVMSetLinkage(data, data_linkage(sym));
 543
 544         LLVMSetInitializer(data, LLVMConstInt(symbol_type(sym), initial_value, 1));
 545
 546         return 0;
 547 }
 548
 549 static int compile(LLVMModuleRef module, struct symbol_list *list)
 550 {
 551         struct symbol *sym;
 552
 553         FOR_EACH_PTR(list, sym) {
 554                 struct entrypoint *ep;
 555                 expand_symbol(sym);
 556                 ep = linearize_symbol(sym);
 557                 if (ep)
 558                         output_fn(module, ep);
 559                 else
 560                         output_data(module, sym);
 561         }
 562         END_FOR_EACH_PTR(sym);
 563
 564         return 0;
 565 }
 566
 567 int main(int argc, char **argv)
 568 {
 569         struct string_list * filelist = NULL;
 570         char *file;
 571
 572         LLVMModuleRef module = LLVMModuleCreateWithName("sparse");
 573
 574         compile(module, sparse_initialize(argc, argv, &filelist));
 575
 576         FOR_EACH_PTR_NOTAG(filelist, file) {
 577                 compile(module, sparse(file));
 578         } END_FOR_EACH_PTR_NOTAG(file);
 579
 580 #if 1
 581         LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0);
 582 #else
 583         LLVMDumpModule(module);
 584 #endif
 585
 586         LLVMDisposeModule(module);
 587
 588         return 0;
 589 }