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