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 <stdbool.h>
  10 #include <stdio.h>
  11 #include <unistd.h>
  12 #include <string.h>
  13 #include <assert.h>
  14
  15 #include "symbol.h"
  16 #include "expression.h"
  17 #include "linearize.h"
  18 #include "flow.h"
  19
  20 struct function {
  21         LLVMBuilderRef                  builder;
  22         LLVMTypeRef                     type;
  23         LLVMValueRef                    fn;
  24         LLVMModuleRef                   module;
  25 };
  26
  27 static inline bool symbol_is_fp_type(struct symbol *sym)
  28 {
  29         if (!sym)
  30                 return false;
  31
  32         return sym->ctype.base_type == &fp_type;
  33 }
  34
  35 static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym);
  36
  37 static LLVMTypeRef func_return_type(LLVMModuleRef module, struct symbol *sym)
  38 {
  39         return symbol_type(module, sym->ctype.base_type);
  40 }
  41
  42 static LLVMTypeRef sym_func_type(LLVMModuleRef module, struct symbol *sym)
  43 {
  44         LLVMTypeRef *arg_type;
  45         LLVMTypeRef func_type;
  46         LLVMTypeRef ret_type;
  47         struct symbol *arg;
  48         int n_arg = 0;
  49
  50         /* to avoid strangeness with varargs [for now], we build
  51          * the function and type anew, for each call.  This
  52          * is probably wrong.  We should look up the
  53          * symbol declaration info.
  54          */
  55
  56         ret_type = func_return_type(module, sym);
  57
  58         /* count args, build argument type information */
  59         FOR_EACH_PTR(sym->arguments, arg) {
  60                 n_arg++;
  61         } END_FOR_EACH_PTR(arg);
  62
  63         arg_type = calloc(n_arg, sizeof(LLVMTypeRef));
  64
  65         int idx = 0;
  66         FOR_EACH_PTR(sym->arguments, arg) {
  67                 struct symbol *arg_sym = arg->ctype.base_type;
  68
  69                 arg_type[idx++] = symbol_type(module, arg_sym);
  70         } END_FOR_EACH_PTR(arg);
  71         func_type = LLVMFunctionType(ret_type, arg_type, n_arg,
  72                                      /* varargs? */ 0);
  73
  74         return func_type;
  75 }
  76
  77 static LLVMTypeRef sym_array_type(LLVMModuleRef module, struct symbol *sym)
  78 {
  79         LLVMTypeRef elem_type;
  80         struct symbol *base_type;
  81
  82         base_type = sym->ctype.base_type;
  83
  84         elem_type = symbol_type(module, base_type);
  85         if (!elem_type)
  86                 return NULL;
  87
  88         return LLVMArrayType(elem_type, sym->bit_size / 8);
  89 }
  90
  91 #define MAX_STRUCT_MEMBERS 64
  92
  93 static LLVMTypeRef sym_struct_type(LLVMModuleRef module, struct symbol *sym)
  94 {
  95         LLVMTypeRef elem_types[MAX_STRUCT_MEMBERS];
  96         struct symbol *member;
  97         char buffer[256];
  98         LLVMTypeRef ret;
  99         unsigned nr = 0;
 100
 101         sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name);
 102
 103         ret = LLVMGetTypeByName(module, buffer);
 104         if (ret)
 105                 return ret;
 106
 107         ret = LLVMStructCreateNamed(LLVMGetGlobalContext(), buffer);
 108
 109         FOR_EACH_PTR(sym->symbol_list, member) {
 110                 LLVMTypeRef member_type;
 111
 112                 assert(nr < MAX_STRUCT_MEMBERS);
 113
 114                 member_type = symbol_type(module, member);
 115
 116                 elem_types[nr++] = member_type;
 117         } END_FOR_EACH_PTR(member);
 118
 119         LLVMStructSetBody(ret, elem_types, nr, 0 /* packed? */);
 120         return ret;
 121 }
 122
 123 static LLVMTypeRef sym_union_type(LLVMModuleRef module, struct symbol *sym)
 124 {
 125         LLVMTypeRef elements;
 126         unsigned union_size;
 127
 128         /*
 129          * There's no union support in the LLVM API so we treat unions as
 130          * opaque structs. The downside is that we lose type information on the
 131          * members but as LLVM doesn't care, neither do we.
 132          */
 133         union_size = sym->bit_size / 8;
 134
 135         elements = LLVMArrayType(LLVMInt8Type(), union_size);
 136
 137         return LLVMStructType(&elements, 1, 0 /* packed? */);
 138 }
 139
 140 static LLVMTypeRef sym_ptr_type(LLVMModuleRef module, struct symbol *sym)
 141 {
 142         LLVMTypeRef type = symbol_type(module, sym->ctype.base_type);
 143
 144         return LLVMPointerType(type, 0);
 145 }
 146
 147 static LLVMTypeRef sym_basetype_type(struct symbol *sym)
 148 {
 149         LLVMTypeRef ret = NULL;
 150
 151         if (symbol_is_fp_type(sym)) {
 152                 switch (sym->bit_size) {
 153                 case 32:
 154                         ret = LLVMFloatType();
 155                         break;
 156                 case 64:
 157                         ret = LLVMDoubleType();
 158                         break;
 159                 case 80:
 160                         ret = LLVMX86FP80Type();
 161                         break;
 162                 default:
 163                         die("invalid bit size %d for type %d", sym->bit_size, sym->type);
 164                         break;
 165                 }
 166         } else {
 167                 switch (sym->bit_size) {
 168                 case -1:        /* 'void *' is treated like 'char *' */
 169                 case 8:
 170                         ret = LLVMInt8Type();
 171                         break;
 172                 case 16:
 173                         ret = LLVMInt16Type();
 174                         break;
 175                 case 32:
 176                         ret = LLVMInt32Type();
 177                         break;
 178                 case 64:
 179                         ret = LLVMInt64Type();
 180                         break;
 181                 default:
 182                         die("invalid bit size %d for type %d", sym->bit_size, sym->type);
 183                         break;
 184                 }
 185         }
 186
 187         return ret;
 188 }
 189
 190 static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym)
 191 {
 192         LLVMTypeRef ret = NULL;
 193
 194         switch (sym->type) {
 195         case SYM_BITFIELD:
 196         case SYM_ENUM:
 197         case SYM_NODE:
 198                 ret = symbol_type(module, sym->ctype.base_type);
 199                 break;
 200         case SYM_BASETYPE:
 201                 ret = sym_basetype_type(sym);
 202                 break;
 203         case SYM_PTR:
 204                 ret = sym_ptr_type(module, sym);
 205                 break;
 206         case SYM_UNION:
 207                 ret = sym_union_type(module, sym);
 208                 break;
 209         case SYM_STRUCT:
 210                 ret = sym_struct_type(module, sym);
 211                 break;
 212         case SYM_ARRAY:
 213                 ret = sym_array_type(module, sym);
 214                 break;
 215         case SYM_FN:
 216                 ret = sym_func_type(module, sym);
 217                 break;
 218         default:
 219                 assert(0);
 220         }
 221         return ret;
 222 }
 223
 224 static LLVMTypeRef insn_symbol_type(LLVMModuleRef module, struct instruction *insn)
 225 {
 226         if (insn->type)
 227                 return symbol_type(module, insn->type);
 228
 229         switch (insn->size) {
 230                 case 8:         return LLVMInt8Type();
 231                 case 16:        return LLVMInt16Type();
 232                 case 32:        return LLVMInt32Type();
 233                 case 64:        return LLVMInt64Type();
 234
 235                 default:
 236                         die("invalid bit size %d", insn->size);
 237                         break;
 238         }
 239
 240         return NULL;    /* not reached */
 241 }
 242
 243 static LLVMLinkage data_linkage(struct symbol *sym)
 244 {
 245         if (sym->ctype.modifiers & MOD_STATIC)
 246                 return LLVMPrivateLinkage;
 247
 248         return LLVMExternalLinkage;
 249 }
 250
 251 static LLVMLinkage function_linkage(struct symbol *sym)
 252 {
 253         if (sym->ctype.modifiers & MOD_STATIC)
 254                 return LLVMInternalLinkage;
 255
 256         return LLVMExternalLinkage;
 257 }
 258
 259 #define MAX_PSEUDO_NAME 64
 260
 261 static void pseudo_name(pseudo_t pseudo, char *buf)
 262 {
 263         switch (pseudo->type) {
 264         case PSEUDO_REG:
 265                 snprintf(buf, MAX_PSEUDO_NAME, "R%d", pseudo->nr);
 266                 break;
 267         case PSEUDO_SYM:
 268                 assert(0);
 269                 break;
 270         case PSEUDO_VAL:
 271                 assert(0);
 272                 break;
 273         case PSEUDO_ARG: {
 274                 assert(0);
 275                 break;
 276         }
 277         case PSEUDO_PHI:
 278                 snprintf(buf, MAX_PSEUDO_NAME, "PHI%d", pseudo->nr);
 279                 break;
 280         default:
 281                 assert(0);
 282         }
 283 }
 284
 285 static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *insn, pseudo_t pseudo)
 286 {
 287         LLVMValueRef result = NULL;
 288
 289         switch (pseudo->type) {
 290         case PSEUDO_REG:
 291                 result = pseudo->priv;
 292                 break;
 293         case PSEUDO_SYM: {
 294                 struct symbol *sym = pseudo->sym;
 295                 struct expression *expr;
 296
 297                 assert(sym->bb_target == NULL);
 298                 assert(sym->ident == NULL);
 299
 300                 expr = sym->initializer;
 301                 if (expr) {
 302                         switch (expr->type) {
 303                         case EXPR_STRING: {
 304                                 const char *s = expr->string->data;
 305                                 LLVMValueRef indices[] = { LLVMConstInt(LLVMInt64Type(), 0, 0), LLVMConstInt(LLVMInt64Type(), 0, 0) };
 306                                 LLVMValueRef data;
 307
 308                                 data = LLVMAddGlobal(fn->module, LLVMArrayType(LLVMInt8Type(), strlen(s) + 1), ".str");
 309                                 LLVMSetLinkage(data, LLVMPrivateLinkage);
 310                                 LLVMSetGlobalConstant(data, 1);
 311                                 LLVMSetInitializer(data, LLVMConstString(strdup(s), strlen(s) + 1, true));
 312
 313                                 result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices));
 314                                 break;
 315                         }
 316                         default:
 317                                 assert(0);
 318                         }
 319                 }
 320                 break;
 321         }
 322         case PSEUDO_VAL:
 323                 result = LLVMConstInt(insn_symbol_type(fn->module, insn), pseudo->value, 1);
 324                 break;
 325         case PSEUDO_ARG: {
 326                 result = LLVMGetParam(fn->fn, pseudo->nr - 1);
 327                 break;
 328         }
 329         case PSEUDO_PHI:
 330                 result = pseudo->priv;
 331                 break;
 332         case PSEUDO_VOID:
 333                 result = NULL;
 334                 break;
 335         default:
 336                 assert(0);
 337         }
 338
 339         return result;
 340 }
 341
 342 static LLVMTypeRef pseudo_type(struct function *fn, struct instruction *insn, pseudo_t pseudo)
 343 {
 344         LLVMValueRef v;
 345         LLVMTypeRef result = NULL;
 346
 347         if (pseudo->priv) {
 348                 v = pseudo->priv;
 349                 return LLVMTypeOf(v);
 350         }
 351
 352         switch (pseudo->type) {
 353         case PSEUDO_REG:
 354                 result = symbol_type(fn->module, pseudo->def->type);
 355                 break;
 356         case PSEUDO_SYM: {
 357                 struct symbol *sym = pseudo->sym;
 358                 struct expression *expr;
 359
 360                 assert(sym->bb_target == NULL);
 361                 assert(sym->ident == NULL);
 362
 363                 expr = sym->initializer;
 364                 if (expr) {
 365                         switch (expr->type) {
 366                         case EXPR_STRING:
 367                                 result = LLVMPointerType(LLVMInt8Type(), 0);
 368                                 break;
 369                         default:
 370                                 assert(0);
 371                         }
 372                 }
 373                 break;
 374         }
 375         case PSEUDO_VAL:
 376                 result = insn_symbol_type(fn->module, insn);
 377                 break;
 378         case PSEUDO_ARG:
 379                 result = LLVMTypeOf(LLVMGetParam(fn->fn, pseudo->nr - 1));
 380                 break;
 381         case PSEUDO_PHI:
 382                 assert(0);
 383                 break;
 384         case PSEUDO_VOID:
 385                 result = LLVMVoidType();
 386                 break;
 387         default:
 388                 assert(0);
 389         }
 390
 391         return result;
 392 }
 393
 394 static void output_op_binary(struct function *fn, struct instruction *insn)
 395 {
 396         LLVMValueRef lhs, rhs, target;
 397         char target_name[64];
 398
 399         lhs = pseudo_to_value(fn, insn, insn->src1);
 400
 401         rhs = pseudo_to_value(fn, insn, insn->src2);
 402
 403         pseudo_name(insn->target, target_name);
 404
 405         switch (insn->opcode) {
 406         /* Binary */
 407         case OP_ADD:
 408                 if (symbol_is_fp_type(insn->type))
 409                         target = LLVMBuildFAdd(fn->builder, lhs, rhs, target_name);
 410                 else
 411                         target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name);
 412                 break;
 413         case OP_SUB:
 414                 if (symbol_is_fp_type(insn->type))
 415                         target = LLVMBuildFSub(fn->builder, lhs, rhs, target_name);
 416                 else
 417                         target = LLVMBuildSub(fn->builder, lhs, rhs, target_name);
 418                 break;
 419         case OP_MULU:
 420                 if (symbol_is_fp_type(insn->type))
 421                         target = LLVMBuildFMul(fn->builder, lhs, rhs, target_name);
 422                 else
 423                         target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
 424                 break;
 425         case OP_MULS:
 426                 assert(!symbol_is_fp_type(insn->type));
 427                 target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
 428                 break;
 429         case OP_DIVU:
 430                 if (symbol_is_fp_type(insn->type))
 431                         target = LLVMBuildFDiv(fn->builder, lhs, rhs, target_name);
 432                 else
 433                         target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name);
 434                 break;
 435         case OP_DIVS:
 436                 assert(!symbol_is_fp_type(insn->type));
 437                 target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name);
 438                 break;
 439         case OP_MODU:
 440                 assert(!symbol_is_fp_type(insn->type));
 441                 target = LLVMBuildURem(fn->builder, lhs, rhs, target_name);
 442                 break;
 443         case OP_MODS:
 444                 assert(!symbol_is_fp_type(insn->type));
 445                 target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name);
 446                 break;
 447         case OP_SHL:
 448                 assert(!symbol_is_fp_type(insn->type));
 449                 target = LLVMBuildShl(fn->builder, lhs, rhs, target_name);
 450                 break;
 451         case OP_LSR:
 452                 assert(!symbol_is_fp_type(insn->type));
 453                 target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name);
 454                 break;
 455         case OP_ASR:
 456                 assert(!symbol_is_fp_type(insn->type));
 457                 target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name);
 458                 break;
 459
 460         /* Logical */
 461         case OP_AND:
 462                 assert(!symbol_is_fp_type(insn->type));
 463                 target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name);
 464                 break;
 465         case OP_OR:
 466                 assert(!symbol_is_fp_type(insn->type));
 467                 target = LLVMBuildOr(fn->builder, lhs, rhs, target_name);
 468                 break;
 469         case OP_XOR:
 470                 assert(!symbol_is_fp_type(insn->type));
 471                 target = LLVMBuildXor(fn->builder, lhs, rhs, target_name);
 472                 break;
 473         case OP_AND_BOOL: {
 474                 LLVMValueRef x, y;
 475
 476                 assert(!symbol_is_fp_type(insn->type));
 477
 478                 y = LLVMBuildICmp(fn->builder, LLVMIntNE, lhs, LLVMConstInt(LLVMTypeOf(lhs), 0, 0), "y");
 479                 x = LLVMBuildICmp(fn->builder, LLVMIntNE, rhs, LLVMConstInt(LLVMTypeOf(rhs), 0, 0), "x");
 480
 481                 target = LLVMBuildAnd(fn->builder, y, x, target_name);
 482                 break;
 483         }
 484         case OP_OR_BOOL: {
 485                 LLVMValueRef tmp;
 486
 487                 assert(!symbol_is_fp_type(insn->type));
 488
 489                 tmp = LLVMBuildOr(fn->builder, rhs, lhs, "tmp");
 490
 491                 target = LLVMBuildICmp(fn->builder, LLVMIntNE, tmp, LLVMConstInt(LLVMTypeOf(tmp), 0, 0), target_name);
 492                 break;
 493         }
 494
 495         /* Binary comparison */
 496         case OP_SET_EQ:
 497                 assert(!symbol_is_fp_type(insn->type));
 498                 target = LLVMBuildICmp(fn->builder, LLVMIntEQ, lhs, rhs, target_name);
 499                 break;
 500         case OP_SET_NE:
 501                 assert(!symbol_is_fp_type(insn->type));
 502                 target = LLVMBuildICmp(fn->builder, LLVMIntNE, lhs, rhs, target_name);
 503                 break;
 504         case OP_SET_LE:
 505                 assert(0);
 506                 break;
 507         case OP_SET_GE:
 508                 assert(0);
 509                 break;
 510         case OP_SET_LT:
 511                 assert(!symbol_is_fp_type(insn->type));
 512                 target = LLVMBuildICmp(fn->builder, LLVMIntSLT, lhs, rhs, target_name);
 513                 break;
 514         case OP_SET_GT:
 515                 assert(!symbol_is_fp_type(insn->type));
 516                 target = LLVMBuildICmp(fn->builder, LLVMIntSGT, lhs, rhs, target_name);
 517                 break;
 518         case OP_SET_B:
 519                 target = LLVMBuildICmp(fn->builder, LLVMIntULT, lhs, rhs, target_name);
 520                 break;
 521         case OP_SET_A:
 522                 target = LLVMBuildICmp(fn->builder, LLVMIntUGT, lhs, rhs, target_name);
 523                 break;
 524         case OP_SET_BE:
 525                 assert(0);
 526                 break;
 527         case OP_SET_AE:
 528                 assert(0);
 529                 break;
 530         default:
 531                 assert(0);
 532                 break;
 533         }
 534
 535         insn->target->priv = target;
 536 }
 537
 538 static void output_op_ret(struct function *fn, struct instruction *insn)
 539 {
 540         pseudo_t pseudo = insn->src;
 541
 542         if (pseudo && pseudo != VOID) {
 543                 LLVMValueRef result = pseudo_to_value(fn, insn, pseudo);
 544
 545                 LLVMBuildRet(fn->builder, result);
 546         } else
 547                 LLVMBuildRetVoid(fn->builder);
 548 }
 549
 550 static void output_op_load(struct function *fn, struct instruction *insn)
 551 {
 552         LLVMTypeRef int_type;
 553         LLVMValueRef src_p, src_i, ofs_i, addr_i, addr, target;
 554
 555         /* int type large enough to hold a pointer */
 556         int_type = LLVMIntType(bits_in_pointer);
 557
 558         /* convert to integer, add src + offset */
 559         src_p = pseudo_to_value(fn, insn, insn->src);
 560         src_i = LLVMBuildPtrToInt(fn->builder, src_p, int_type, "src_i");
 561
 562         ofs_i = LLVMConstInt(int_type, insn->offset, 0);
 563         addr_i = LLVMBuildAdd(fn->builder, src_i, ofs_i, "addr_i");
 564
 565         /* convert address back to pointer */
 566         addr = LLVMBuildIntToPtr(fn->builder, addr_i,
 567                                  LLVMPointerType(int_type, 0), "addr");
 568
 569         /* perform load */
 570         target = LLVMBuildLoad(fn->builder, addr, "load_target");
 571
 572         insn->target->priv = target;
 573 }
 574
 575 static void output_op_store(struct function *fn, struct instruction *insn)
 576 {
 577         LLVMTypeRef int_type;
 578         LLVMValueRef src_p, src_i, ofs_i, addr_i, addr, target, target_in;
 579
 580         /* int type large enough to hold a pointer */
 581         int_type = LLVMIntType(bits_in_pointer);
 582
 583         /* convert to integer, add src + offset */
 584         src_p = pseudo_to_value(fn, insn, insn->src);
 585         src_i = LLVMBuildPtrToInt(fn->builder, src_p, int_type, "src_i");
 586
 587         ofs_i = LLVMConstInt(int_type, insn->offset, 0);
 588         addr_i = LLVMBuildAdd(fn->builder, src_i, ofs_i, "addr_i");
 589
 590         /* convert address back to pointer */
 591         addr = LLVMBuildIntToPtr(fn->builder, addr_i,
 592                                  LLVMPointerType(int_type, 0), "addr");
 593
 594         target_in = pseudo_to_value(fn, insn, insn->target);
 595
 596         /* perform store */
 597         target = LLVMBuildStore(fn->builder, target_in, addr);
 598
 599         insn->target->priv = target;
 600 }
 601
 602 static void output_op_br(struct function *fn, struct instruction *br)
 603 {
 604         if (br->cond) {
 605                 LLVMValueRef cond = pseudo_to_value(fn, br, br->cond);
 606
 607                 LLVMBuildCondBr(fn->builder, cond,
 608                                 br->bb_true->priv,
 609                                 br->bb_false->priv);
 610         } else
 611                 LLVMBuildBr(fn->builder,
 612                             br->bb_true ? br->bb_true->priv :
 613                             br->bb_false->priv);
 614 }
 615
 616 static void output_op_sel(struct function *fn, struct instruction *insn)
 617 {
 618         LLVMValueRef target, src1, src2, src3;
 619
 620         src1 = pseudo_to_value(fn, insn, insn->src1);
 621         src2 = pseudo_to_value(fn, insn, insn->src2);
 622         src3 = pseudo_to_value(fn, insn, insn->src3);
 623
 624         target = LLVMBuildSelect(fn->builder, src1, src2, src3, "select");
 625
 626         insn->target->priv = target;
 627 }
 628
 629 static void output_op_switch(struct function *fn, struct instruction *insn)
 630 {
 631         LLVMValueRef sw_val, target;
 632         struct basic_block *def = NULL;
 633         struct multijmp *jmp;
 634         int n_jmp = 0;
 635
 636         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 637                 if (jmp->begin == jmp->end) {           /* case N */
 638                         n_jmp++;
 639                 } else if (jmp->begin < jmp->end) {     /* case M..N */
 640                         assert(0);
 641                 } else                                  /* default case */
 642                         def = jmp->target;
 643         } END_FOR_EACH_PTR(jmp);
 644
 645         sw_val = pseudo_to_value(fn, insn, insn->target);
 646         target = LLVMBuildSwitch(fn->builder, sw_val,
 647                                  def ? def->priv : NULL, n_jmp);
 648
 649         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 650                 if (jmp->begin == jmp->end) {           /* case N */
 651                         LLVMAddCase(target,
 652                                 LLVMConstInt(LLVMInt32Type(), jmp->begin, 0),
 653                                 jmp->target->priv);
 654                 } else if (jmp->begin < jmp->end) {     /* case M..N */
 655                         assert(0);
 656                 }
 657         } END_FOR_EACH_PTR(jmp);
 658
 659         insn->target->priv = target;
 660 }
 661
 662 struct llfunc {
 663         char            name[256];      /* wasteful */
 664         LLVMValueRef    func;
 665 };
 666
 667 DECLARE_ALLOCATOR(llfunc);
 668 DECLARE_PTR_LIST(llfunc_list, struct llfunc);
 669 ALLOCATOR(llfunc, "llfuncs");
 670
 671 static struct local_module {
 672         struct llfunc_list      *llfunc_list;
 673 } mi;
 674
 675 static LLVMTypeRef get_func_type(struct function *fn, struct instruction *insn)
 676 {
 677         struct symbol *sym = insn->func->sym;
 678         char buffer[256];
 679         LLVMTypeRef func_type, ret_type;
 680         struct pseudo *arg;
 681         int n_arg = 0;
 682         LLVMTypeRef *arg_type;
 683
 684         if (sym->ident)
 685                 sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name);
 686         else
 687                 sprintf(buffer, "<anon sym %p>", sym);
 688
 689         /* VERIFY: is this correct, for functions? */
 690         func_type = LLVMGetTypeByName(fn->module, buffer);
 691         if (func_type)
 692                 return func_type;
 693
 694         /* to avoid strangeness with varargs [for now], we build
 695          * the function and type anew, for each call.  This
 696          * is probably wrong.  We should look up the
 697          * symbol declaration info.
 698          */
 699
 700         /* build return type */
 701         if (insn->target && insn->target != VOID)
 702                 ret_type = pseudo_type(fn, insn, insn->target);
 703         else
 704                 ret_type = LLVMVoidType();
 705
 706         /* count args, build argument type information */
 707         FOR_EACH_PTR(insn->arguments, arg) {
 708                 n_arg++;
 709         } END_FOR_EACH_PTR(arg);
 710
 711         arg_type = calloc(n_arg, sizeof(LLVMTypeRef));
 712
 713         int idx = 0;
 714         FOR_EACH_PTR(insn->arguments, arg) {
 715                 arg_type[idx++] = pseudo_type(fn, insn, arg);
 716         } END_FOR_EACH_PTR(arg);
 717
 718         func_type = LLVMFunctionType(ret_type, arg_type, n_arg,
 719                                      /* varargs? */ 0);
 720
 721         return func_type;
 722 }
 723
 724 static LLVMValueRef get_function(struct function *fn, struct instruction *insn)
 725 {
 726         struct symbol *sym = insn->func->sym;
 727         char buffer[256];
 728         LLVMValueRef func;
 729         struct llfunc *f;
 730
 731         if (sym->ident)
 732                 sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name);
 733         else
 734                 sprintf(buffer, "<anon sym %p>", sym);
 735
 736
 737         /* search for pre-built function type definition */
 738         FOR_EACH_PTR(mi.llfunc_list, f) {
 739                 if (!strcmp(f->name, buffer))
 740                         return f->func;         /* found match; return */
 741         } END_FOR_EACH_PTR(f);
 742
 743         /* build function type definition */
 744         LLVMTypeRef func_type = get_func_type(fn, insn);
 745
 746         func = LLVMAddFunction(fn->module, buffer, func_type);
 747
 748         /* store built function on list, for later referencing */
 749         f = calloc(1, sizeof(*f));
 750         strncpy(f->name, buffer, sizeof(f->name) - 1);
 751         f->func = func;
 752
 753         add_ptr_list(&mi.llfunc_list, f);
 754
 755         return func;
 756 }
 757
 758 static void output_op_call(struct function *fn, struct instruction *insn)
 759 {
 760         LLVMValueRef target, func;
 761         int n_arg = 0, i;
 762         struct pseudo *arg;
 763         LLVMValueRef *args;
 764
 765         FOR_EACH_PTR(insn->arguments, arg) {
 766                 n_arg++;
 767         } END_FOR_EACH_PTR(arg);
 768
 769         args = calloc(n_arg, sizeof(LLVMValueRef));
 770
 771         i = 0;
 772         FOR_EACH_PTR(insn->arguments, arg) {
 773                 args[i++] = pseudo_to_value(fn, insn, arg);
 774         } END_FOR_EACH_PTR(arg);
 775
 776         func = get_function(fn, insn);
 777         target = LLVMBuildCall(fn->builder, func, args, n_arg, "");
 778
 779         insn->target->priv = target;
 780 }
 781
 782 static void output_op_phi(struct function *fn, struct instruction *insn)
 783 {
 784         pseudo_t phi;
 785         LLVMValueRef target;
 786
 787         target = LLVMBuildPhi(fn->builder, insn_symbol_type(fn->module, insn),
 788                                 "phi");
 789         int pll = 0;
 790         FOR_EACH_PTR(insn->phi_list, phi) {
 791                 if (pseudo_to_value(fn, insn, phi))     /* skip VOID */
 792                         pll++;
 793         } END_FOR_EACH_PTR(phi);
 794
 795         LLVMValueRef *phi_vals = calloc(pll, sizeof(LLVMValueRef));
 796         LLVMBasicBlockRef *phi_blks = calloc(pll, sizeof(LLVMBasicBlockRef));
 797
 798         int idx = 0;
 799         FOR_EACH_PTR(insn->phi_list, phi) {
 800                 LLVMValueRef v;
 801
 802                 v = pseudo_to_value(fn, insn, phi);
 803                 if (v) {                        /* skip VOID */
 804                         phi_vals[idx] = v;
 805                         phi_blks[idx] = phi->def->bb->priv;
 806                         idx++;
 807                 }
 808         } END_FOR_EACH_PTR(phi);
 809
 810         LLVMAddIncoming(target, phi_vals, phi_blks, pll);
 811
 812         insn->target->priv = target;
 813 }
 814
 815 static void output_op_ptrcast(struct function *fn, struct instruction *insn)
 816 {
 817         LLVMValueRef src, target;
 818         char target_name[64];
 819
 820         src = insn->src->priv;
 821         if (!src)
 822                 src = pseudo_to_value(fn, insn, insn->src);
 823
 824         pseudo_name(insn->target, target_name);
 825
 826         assert(!symbol_is_fp_type(insn->type));
 827
 828         target = LLVMBuildBitCast(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
 829
 830         insn->target->priv = target;
 831 }
 832
 833 static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op)
 834 {
 835         LLVMValueRef src, target;
 836         char target_name[64];
 837
 838         src = insn->src->priv;
 839         if (!src)
 840                 src = pseudo_to_value(fn, insn, insn->src);
 841
 842         pseudo_name(insn->target, target_name);
 843
 844         assert(!symbol_is_fp_type(insn->type));
 845
 846         if (insn->size < LLVMGetIntTypeWidth(LLVMTypeOf(src)))
 847                 target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
 848         else
 849                 target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(fn->module, insn), target_name);
 850
 851         insn->target->priv = target;
 852 }
 853
 854 static void output_op_copy(struct function *fn, struct instruction *insn,
 855                            pseudo_t pseudo)
 856 {
 857         LLVMValueRef src, target;
 858         LLVMTypeRef const_type;
 859         char target_name[64];
 860
 861         pseudo_name(insn->target, target_name);
 862         src = pseudo_to_value(fn, insn, pseudo);
 863         const_type = insn_symbol_type(fn->module, insn);
 864
 865         /*
 866          * This is nothing more than 'target = src'
 867          *
 868          * TODO: find a better way to provide an identity function,
 869          * than using "X + 0" simply to produce a new LLVM pseudo
 870          */
 871
 872         if (symbol_is_fp_type(insn->type))
 873                 target = LLVMBuildFAdd(fn->builder, src,
 874                         LLVMConstReal(const_type, 0.0), target_name);
 875         else
 876                 target = LLVMBuildAdd(fn->builder, src,
 877                         LLVMConstInt(const_type, 0, 0), target_name);
 878
 879         insn->target->priv = target;
 880 }
 881
 882 static void output_insn(struct function *fn, struct instruction *insn)
 883 {
 884         switch (insn->opcode) {
 885         case OP_RET:
 886                 output_op_ret(fn, insn);
 887                 break;
 888         case OP_BR:
 889                 output_op_br(fn, insn);
 890                 break;
 891         case OP_SYMADDR:
 892                 assert(0);
 893                 break;
 894         case OP_SETVAL:
 895                 assert(0);
 896                 break;
 897         case OP_SWITCH:
 898                 output_op_switch(fn, insn);
 899                 break;
 900         case OP_COMPUTEDGOTO:
 901                 assert(0);
 902                 break;
 903         case OP_PHISOURCE:
 904                 /* target = src */
 905                 insn->target->priv = pseudo_to_value(fn, insn, insn->phi_src);
 906                 break;
 907         case OP_PHI:
 908                 output_op_phi(fn, insn);
 909                 break;
 910         case OP_LOAD:
 911                 output_op_load(fn, insn);
 912                 break;
 913         case OP_LNOP:
 914                 assert(0);
 915                 break;
 916         case OP_STORE:
 917                 output_op_store(fn, insn);
 918                 break;
 919         case OP_SNOP:
 920                 assert(0);
 921                 break;
 922         case OP_INLINED_CALL:
 923                 assert(0);
 924                 break;
 925         case OP_CALL:
 926                 output_op_call(fn, insn);
 927                 break;
 928         case OP_CAST:
 929                 output_op_cast(fn, insn, LLVMZExt);
 930                 break;
 931         case OP_SCAST:
 932                 output_op_cast(fn, insn, LLVMSExt);
 933                 break;
 934         case OP_FPCAST:
 935                 assert(0);
 936                 break;
 937         case OP_PTRCAST:
 938                 output_op_ptrcast(fn, insn);
 939                 break;
 940         case OP_BINARY ... OP_BINARY_END:
 941         case OP_BINCMP ... OP_BINCMP_END:
 942                 output_op_binary(fn, insn);
 943                 break;
 944         case OP_SEL:
 945                 output_op_sel(fn, insn);
 946                 break;
 947         case OP_SLICE:
 948                 assert(0);
 949                 break;
 950         case OP_NOT: {
 951                 LLVMValueRef src, target;
 952                 char target_name[64];
 953
 954                 src = pseudo_to_value(fn, insn, insn->src);
 955
 956                 pseudo_name(insn->target, target_name);
 957
 958                 target = LLVMBuildNot(fn->builder, src, target_name);
 959
 960                 insn->target->priv = target;
 961                 break;
 962         }
 963         case OP_NEG:
 964                 assert(0);
 965                 break;
 966         case OP_CONTEXT:
 967                 assert(0);
 968                 break;
 969         case OP_RANGE:
 970                 assert(0);
 971                 break;
 972         case OP_NOP:
 973                 assert(0);
 974                 break;
 975         case OP_DEATHNOTE:
 976                 assert(0);
 977                 break;
 978         case OP_ASM:
 979                 assert(0);
 980                 break;
 981         case OP_COPY:
 982                 output_op_copy(fn, insn, insn->src);
 983                 break;
 984         default:
 985                 break;
 986         }
 987 }
 988
 989 static void output_bb(struct function *fn, struct basic_block *bb, unsigned long generation)
 990 {
 991         struct instruction *insn;
 992
 993         bb->generation = generation;
 994
 995         FOR_EACH_PTR(bb->insns, insn) {
 996                 if (!insn->bb)
 997                         continue;
 998
 999                 output_insn(fn, insn);
1000         }
1001         END_FOR_EACH_PTR(insn);
1002 }
1003
1004 #define MAX_ARGS        64
1005
1006 static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
1007 {
1008         unsigned long generation = ++bb_generation;
1009         struct symbol *sym = ep->name;
1010         struct symbol *base_type = sym->ctype.base_type;
1011         struct symbol *ret_type = sym->ctype.base_type->ctype.base_type;
1012         LLVMTypeRef arg_types[MAX_ARGS];
1013         LLVMTypeRef return_type;
1014         struct function function;
1015         struct basic_block *bb;
1016         struct symbol *arg;
1017         const char *name;
1018         int nr_args = 0;
1019         struct llfunc *f;
1020
1021         FOR_EACH_PTR(base_type->arguments, arg) {
1022                 struct symbol *arg_base_type = arg->ctype.base_type;
1023
1024                 arg_types[nr_args++] = symbol_type(module, arg_base_type);
1025         } END_FOR_EACH_PTR(arg);
1026
1027         name = show_ident(sym->ident);
1028
1029         return_type = symbol_type(module, ret_type);
1030
1031         function.module = module;
1032
1033         function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0);
1034
1035         function.fn = LLVMAddFunction(module, name, function.type);
1036         LLVMSetFunctionCallConv(function.fn, LLVMCCallConv);
1037
1038         LLVMSetLinkage(function.fn, function_linkage(sym));
1039
1040         /* store built function on list, for later referencing */
1041         f = calloc(1, sizeof(*f));
1042         strncpy(f->name, name, sizeof(f->name) - 1);
1043         f->func = function.fn;
1044
1045         add_ptr_list(&mi.llfunc_list, f);
1046
1047         function.builder = LLVMCreateBuilder();
1048
1049         static int nr_bb;
1050
1051         FOR_EACH_PTR(ep->bbs, bb) {
1052                 if (bb->generation == generation)
1053                         continue;
1054
1055                 LLVMBasicBlockRef bbr;
1056                 char bbname[32];
1057
1058                 sprintf(bbname, "L%d", nr_bb++);
1059                 bbr = LLVMAppendBasicBlock(function.fn, bbname);
1060
1061                 bb->priv = bbr;
1062         }
1063         END_FOR_EACH_PTR(bb);
1064
1065         FOR_EACH_PTR(ep->bbs, bb) {
1066                 if (bb->generation == generation)
1067                         continue;
1068
1069                 LLVMPositionBuilderAtEnd(function.builder, bb->priv);
1070
1071                 output_bb(&function, bb, generation);
1072         }
1073         END_FOR_EACH_PTR(bb);
1074 }
1075
1076 static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym)
1077 {
1078         struct expression *initializer = sym->initializer;
1079         LLVMValueRef initial_value;
1080         LLVMValueRef data;
1081         const char *name;
1082
1083         if (initializer) {
1084                 switch (initializer->type) {
1085                 case EXPR_VALUE:
1086                         initial_value = LLVMConstInt(symbol_type(module, sym), initializer->value, 1);
1087                         break;
1088                 case EXPR_SYMBOL: {
1089                         struct symbol *sym = initializer->symbol;
1090
1091                         initial_value = LLVMGetNamedGlobal(module, show_ident(sym->ident));
1092                         if (!initial_value)
1093                                 initial_value = output_data(module, sym);
1094                         break;
1095                 }
1096                 default:
1097                         assert(0);
1098                 }
1099         } else {
1100                 LLVMTypeRef type = symbol_type(module, sym);
1101
1102                 initial_value = LLVMConstNull(type);
1103         }
1104
1105         name = show_ident(sym->ident);
1106
1107         data = LLVMAddGlobal(module, symbol_type(module, sym->ctype.base_type), name);
1108
1109         LLVMSetLinkage(data, data_linkage(sym));
1110
1111         if (!(sym->ctype.modifiers & MOD_EXTERN))
1112                 LLVMSetInitializer(data, initial_value);
1113
1114         return data;
1115 }
1116
1117 static int compile(LLVMModuleRef module, struct symbol_list *list)
1118 {
1119         struct symbol *sym;
1120
1121         FOR_EACH_PTR(list, sym) {
1122                 struct entrypoint *ep;
1123                 expand_symbol(sym);
1124                 ep = linearize_symbol(sym);
1125                 if (ep)
1126                         output_fn(module, ep);
1127                 else
1128                         output_data(module, sym);
1129         }
1130         END_FOR_EACH_PTR(sym);
1131
1132         return 0;
1133 }
1134
1135 int main(int argc, char **argv)
1136 {
1137         struct string_list * filelist = NULL;
1138         char *file;
1139
1140         LLVMModuleRef module = LLVMModuleCreateWithName("sparse");
1141
1142         compile(module, sparse_initialize(argc, argv, &filelist));
1143
1144         FOR_EACH_PTR_NOTAG(filelist, file) {
1145                 compile(module, sparse(file));
1146         } END_FOR_EACH_PTR_NOTAG(file);
1147
1148         LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0);
1149
1150         LLVMDisposeModule(module);
1151
1152         return 0;
1153 }