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                 assert(sym->ident == NULL);
 312
 313                 expr = sym->initializer;
 314                 if (expr) {
 315                         switch (expr->type) {
 316                         case EXPR_STRING: {
 317                                 const char *s = expr->string->data;
 318                                 LLVMValueRef indices[] = { LLVMConstInt(LLVMInt64Type(), 0, 0), LLVMConstInt(LLVMInt64Type(), 0, 0) };
 319                                 LLVMValueRef data;
 320
 321                                 data = LLVMAddGlobal(fn->module, LLVMArrayType(LLVMInt8Type(), strlen(s) + 1), ".str");
 322                                 LLVMSetLinkage(data, LLVMPrivateLinkage);
 323                                 LLVMSetGlobalConstant(data, 1);
 324                                 LLVMSetInitializer(data, LLVMConstString(strdup(s), strlen(s) + 1, true));
 325
 326                                 result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices));
 327                                 break;
 328                         }
 329                         default:
 330                                 assert(0);
 331                         }
 332                 }
 333                 break;
 334         }
 335         case PSEUDO_VAL:
 336                 result = LLVMConstInt(insn_symbol_type(fn->module, insn), pseudo->value, 1);
 337                 break;
 338         case PSEUDO_ARG: {
 339                 result = LLVMGetParam(fn->fn, pseudo->nr - 1);
 340                 break;
 341         }
 342         case PSEUDO_PHI:
 343                 result = pseudo->priv;
 344                 break;
 345         case PSEUDO_VOID:
 346                 result = NULL;
 347                 break;
 348         default:
 349                 assert(0);
 350         }
 351
 352         return result;
 353 }
 354
 355 static LLVMTypeRef pseudo_type(struct function *fn, struct instruction *insn, pseudo_t pseudo)
 356 {
 357         LLVMValueRef v;
 358         LLVMTypeRef result = NULL;
 359
 360         if (pseudo->priv) {
 361                 v = pseudo->priv;
 362                 return LLVMTypeOf(v);
 363         }
 364
 365         switch (pseudo->type) {
 366         case PSEUDO_REG:
 367                 result = symbol_type(fn->module, pseudo->def->type);
 368                 break;
 369         case PSEUDO_SYM: {
 370                 struct symbol *sym = pseudo->sym;
 371                 struct expression *expr;
 372
 373                 assert(sym->bb_target == NULL);
 374                 assert(sym->ident == NULL);
 375
 376                 expr = sym->initializer;
 377                 if (expr) {
 378                         switch (expr->type) {
 379                         case EXPR_STRING:
 380                                 result = LLVMPointerType(LLVMInt8Type(), 0);
 381                                 break;
 382                         default:
 383                                 assert(0);
 384                         }
 385                 }
 386                 break;
 387         }
 388         case PSEUDO_VAL:
 389                 result = insn_symbol_type(fn->module, insn);
 390                 break;
 391         case PSEUDO_ARG:
 392                 result = LLVMTypeOf(LLVMGetParam(fn->fn, pseudo->nr - 1));
 393                 break;
 394         case PSEUDO_PHI:
 395                 assert(0);
 396                 break;
 397         case PSEUDO_VOID:
 398                 result = LLVMVoidType();
 399                 break;
 400         default:
 401                 assert(0);
 402         }
 403
 404         return result;
 405 }
 406
 407 static LLVMRealPredicate translate_fop(int opcode)
 408 {
 409         static const LLVMRealPredicate trans_tbl[] = {
 410                 [OP_SET_EQ]     = LLVMRealOEQ,
 411                 [OP_SET_NE]     = LLVMRealUNE,
 412                 [OP_SET_LE]     = LLVMRealOLE,
 413                 [OP_SET_GE]     = LLVMRealOGE,
 414                 [OP_SET_LT]     = LLVMRealOLT,
 415                 [OP_SET_GT]     = LLVMRealOGT,
 416                 /* Are these used with FP? */
 417                 [OP_SET_B]      = LLVMRealOLT,
 418                 [OP_SET_A]      = LLVMRealOGT,
 419                 [OP_SET_BE]     = LLVMRealOLE,
 420                 [OP_SET_AE]     = LLVMRealOGE,
 421         };
 422
 423         return trans_tbl[opcode];
 424 }
 425
 426 static LLVMIntPredicate translate_op(int opcode)
 427 {
 428         static const LLVMIntPredicate trans_tbl[] = {
 429                 [OP_SET_EQ]     = LLVMIntEQ,
 430                 [OP_SET_NE]     = LLVMIntNE,
 431                 [OP_SET_LE]     = LLVMIntSLE,
 432                 [OP_SET_GE]     = LLVMIntSGE,
 433                 [OP_SET_LT]     = LLVMIntSLT,
 434                 [OP_SET_GT]     = LLVMIntSGT,
 435                 [OP_SET_B]      = LLVMIntULT,
 436                 [OP_SET_A]      = LLVMIntUGT,
 437                 [OP_SET_BE]     = LLVMIntULE,
 438                 [OP_SET_AE]     = LLVMIntUGE,
 439         };
 440
 441         return trans_tbl[opcode];
 442 }
 443
 444 static void output_op_binary(struct function *fn, struct instruction *insn)
 445 {
 446         LLVMValueRef lhs, rhs, target;
 447         char target_name[64];
 448
 449         lhs = pseudo_to_value(fn, insn, insn->src1);
 450
 451         rhs = pseudo_to_value(fn, insn, insn->src2);
 452
 453         pseudo_name(insn->target, target_name);
 454
 455         switch (insn->opcode) {
 456         /* Binary */
 457         case OP_ADD:
 458                 if (symbol_is_fp_type(insn->type))
 459                         target = LLVMBuildFAdd(fn->builder, lhs, rhs, target_name);
 460                 else
 461                         target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name);
 462                 break;
 463         case OP_SUB:
 464                 if (symbol_is_fp_type(insn->type))
 465                         target = LLVMBuildFSub(fn->builder, lhs, rhs, target_name);
 466                 else
 467                         target = LLVMBuildSub(fn->builder, lhs, rhs, target_name);
 468                 break;
 469         case OP_MULU:
 470                 if (symbol_is_fp_type(insn->type))
 471                         target = LLVMBuildFMul(fn->builder, lhs, rhs, target_name);
 472                 else
 473                         target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
 474                 break;
 475         case OP_MULS:
 476                 assert(!symbol_is_fp_type(insn->type));
 477                 target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
 478                 break;
 479         case OP_DIVU:
 480                 if (symbol_is_fp_type(insn->type))
 481                         target = LLVMBuildFDiv(fn->builder, lhs, rhs, target_name);
 482                 else
 483                         target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name);
 484                 break;
 485         case OP_DIVS:
 486                 assert(!symbol_is_fp_type(insn->type));
 487                 target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name);
 488                 break;
 489         case OP_MODU:
 490                 assert(!symbol_is_fp_type(insn->type));
 491                 target = LLVMBuildURem(fn->builder, lhs, rhs, target_name);
 492                 break;
 493         case OP_MODS:
 494                 assert(!symbol_is_fp_type(insn->type));
 495                 target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name);
 496                 break;
 497         case OP_SHL:
 498                 assert(!symbol_is_fp_type(insn->type));
 499                 target = LLVMBuildShl(fn->builder, lhs, rhs, target_name);
 500                 break;
 501         case OP_LSR:
 502                 assert(!symbol_is_fp_type(insn->type));
 503                 target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name);
 504                 break;
 505         case OP_ASR:
 506                 assert(!symbol_is_fp_type(insn->type));
 507                 target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name);
 508                 break;
 509
 510         /* Logical */
 511         case OP_AND:
 512                 assert(!symbol_is_fp_type(insn->type));
 513                 target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name);
 514                 break;
 515         case OP_OR:
 516                 assert(!symbol_is_fp_type(insn->type));
 517                 target = LLVMBuildOr(fn->builder, lhs, rhs, target_name);
 518                 break;
 519         case OP_XOR:
 520                 assert(!symbol_is_fp_type(insn->type));
 521                 target = LLVMBuildXor(fn->builder, lhs, rhs, target_name);
 522                 break;
 523         case OP_AND_BOOL: {
 524                 LLVMValueRef x, y;
 525
 526                 assert(!symbol_is_fp_type(insn->type));
 527
 528                 y = LLVMBuildICmp(fn->builder, LLVMIntNE, lhs, LLVMConstInt(LLVMTypeOf(lhs), 0, 0), "y");
 529                 x = LLVMBuildICmp(fn->builder, LLVMIntNE, rhs, LLVMConstInt(LLVMTypeOf(rhs), 0, 0), "x");
 530
 531                 target = LLVMBuildAnd(fn->builder, y, x, target_name);
 532                 break;
 533         }
 534         case OP_OR_BOOL: {
 535                 LLVMValueRef tmp;
 536
 537                 assert(!symbol_is_fp_type(insn->type));
 538
 539                 tmp = LLVMBuildOr(fn->builder, rhs, lhs, "tmp");
 540
 541                 target = LLVMBuildICmp(fn->builder, LLVMIntNE, tmp, LLVMConstInt(LLVMTypeOf(tmp), 0, 0), target_name);
 542                 break;
 543         }
 544
 545         /* Binary comparison */
 546         case OP_BINCMP ... OP_BINCMP_END: {
 547                 if (LLVMGetTypeKind(LLVMTypeOf(lhs)) == LLVMIntegerTypeKind) {
 548                         LLVMIntPredicate op = translate_op(insn->opcode);
 549
 550                         target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name);
 551                 } else {
 552                         LLVMRealPredicate op = translate_fop(insn->opcode);
 553
 554                         target = LLVMBuildFCmp(fn->builder, op, lhs, rhs, target_name);
 555                 }
 556                 break;
 557         }
 558         default:
 559                 assert(0);
 560                 break;
 561         }
 562
 563         insn->target->priv = target;
 564 }
 565
 566 static void output_op_ret(struct function *fn, struct instruction *insn)
 567 {
 568         pseudo_t pseudo = insn->src;
 569
 570         if (pseudo && pseudo != VOID) {
 571                 LLVMValueRef result = pseudo_to_value(fn, insn, pseudo);
 572
 573                 LLVMBuildRet(fn->builder, result);
 574         } else
 575                 LLVMBuildRetVoid(fn->builder);
 576 }
 577
 578 static void output_op_load(struct function *fn, struct instruction *insn)
 579 {
 580         LLVMTypeRef int_type;
 581         LLVMValueRef src_p, src_i, ofs_i, addr_i, addr, target;
 582
 583         /* int type large enough to hold a pointer */
 584         int_type = LLVMIntType(bits_in_pointer);
 585
 586         /* convert to integer, add src + offset */
 587         src_p = pseudo_to_value(fn, insn, insn->src);
 588         src_i = LLVMBuildPtrToInt(fn->builder, src_p, int_type, "src_i");
 589
 590         ofs_i = LLVMConstInt(int_type, insn->offset, 0);
 591         addr_i = LLVMBuildAdd(fn->builder, src_i, ofs_i, "addr_i");
 592
 593         /* convert address back to pointer */
 594         addr = LLVMBuildIntToPtr(fn->builder, addr_i,
 595                                  LLVMPointerType(int_type, 0), "addr");
 596
 597         /* perform load */
 598         target = LLVMBuildLoad(fn->builder, addr, "load_target");
 599
 600         insn->target->priv = target;
 601 }
 602
 603 static void output_op_store(struct function *fn, struct instruction *insn)
 604 {
 605         LLVMTypeRef int_type;
 606         LLVMValueRef src_p, src_i, ofs_i, addr_i, addr, target, target_in;
 607
 608         /* int type large enough to hold a pointer */
 609         int_type = LLVMIntType(bits_in_pointer);
 610
 611         /* convert to integer, add src + offset */
 612         src_p = pseudo_to_value(fn, insn, insn->src);
 613         src_i = LLVMBuildPtrToInt(fn->builder, src_p, int_type, "src_i");
 614
 615         ofs_i = LLVMConstInt(int_type, insn->offset, 0);
 616         addr_i = LLVMBuildAdd(fn->builder, src_i, ofs_i, "addr_i");
 617
 618         /* convert address back to pointer */
 619         addr = LLVMBuildIntToPtr(fn->builder, addr_i,
 620                                  LLVMPointerType(int_type, 0), "addr");
 621
 622         target_in = pseudo_to_value(fn, insn, insn->target);
 623
 624         /* perform store */
 625         target = LLVMBuildStore(fn->builder, target_in, addr);
 626
 627         insn->target->priv = target;
 628 }
 629
 630 static void output_op_br(struct function *fn, struct instruction *br)
 631 {
 632         if (br->cond) {
 633                 LLVMValueRef cond = pseudo_to_value(fn, br, br->cond);
 634
 635                 LLVMBuildCondBr(fn->builder, cond,
 636                                 br->bb_true->priv,
 637                                 br->bb_false->priv);
 638         } else
 639                 LLVMBuildBr(fn->builder,
 640                             br->bb_true ? br->bb_true->priv :
 641                             br->bb_false->priv);
 642 }
 643
 644 static void output_op_sel(struct function *fn, struct instruction *insn)
 645 {
 646         LLVMValueRef target, src1, src2, src3;
 647
 648         src1 = pseudo_to_value(fn, insn, insn->src1);
 649         src2 = pseudo_to_value(fn, insn, insn->src2);
 650         src3 = pseudo_to_value(fn, insn, insn->src3);
 651
 652         target = LLVMBuildSelect(fn->builder, src1, src2, src3, "select");
 653
 654         insn->target->priv = target;
 655 }
 656
 657 static void output_op_switch(struct function *fn, struct instruction *insn)
 658 {
 659         LLVMValueRef sw_val, target;
 660         struct basic_block *def = NULL;
 661         struct multijmp *jmp;
 662         int n_jmp = 0;
 663
 664         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 665                 if (jmp->begin == jmp->end) {           /* case N */
 666                         n_jmp++;
 667                 } else if (jmp->begin < jmp->end) {     /* case M..N */
 668                         assert(0);
 669                 } else                                  /* default case */
 670                         def = jmp->target;
 671         } END_FOR_EACH_PTR(jmp);
 672
 673         sw_val = pseudo_to_value(fn, insn, insn->target);
 674         target = LLVMBuildSwitch(fn->builder, sw_val,
 675                                  def ? def->priv : NULL, n_jmp);
 676
 677         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 678                 if (jmp->begin == jmp->end) {           /* case N */
 679                         LLVMAddCase(target,
 680                                 LLVMConstInt(LLVMInt32Type(), jmp->begin, 0),
 681                                 jmp->target->priv);
 682                 } else if (jmp->begin < jmp->end) {     /* case M..N */
 683                         assert(0);
 684                 }
 685         } END_FOR_EACH_PTR(jmp);
 686
 687         insn->target->priv = target;
 688 }
 689
 690 struct llfunc {
 691         char            name[256];      /* wasteful */
 692         LLVMValueRef    func;
 693 };
 694
 695 DECLARE_ALLOCATOR(llfunc);
 696 DECLARE_PTR_LIST(llfunc_list, struct llfunc);
 697 ALLOCATOR(llfunc, "llfuncs");
 698
 699 static struct local_module {
 700         struct llfunc_list      *llfunc_list;
 701 } mi;
 702
 703 static LLVMTypeRef get_func_type(struct function *fn, struct instruction *insn)
 704 {
 705         struct symbol *sym = insn->func->sym;
 706         char buffer[256];
 707         LLVMTypeRef func_type, ret_type;
 708         struct pseudo *arg;
 709         int n_arg = 0;
 710         LLVMTypeRef *arg_type;
 711
 712         if (sym->ident)
 713                 sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name);
 714         else
 715                 sprintf(buffer, "<anon sym %p>", sym);
 716
 717         /* VERIFY: is this correct, for functions? */
 718         func_type = LLVMGetTypeByName(fn->module, buffer);
 719         if (func_type)
 720                 return func_type;
 721
 722         /* to avoid strangeness with varargs [for now], we build
 723          * the function and type anew, for each call.  This
 724          * is probably wrong.  We should look up the
 725          * symbol declaration info.
 726          */
 727
 728         /* build return type */
 729         if (insn->target && insn->target != VOID)
 730                 ret_type = pseudo_type(fn, insn, insn->target);
 731         else
 732                 ret_type = LLVMVoidType();
 733
 734         /* count args, build argument type information */
 735         FOR_EACH_PTR(insn->arguments, arg) {
 736                 n_arg++;
 737         } END_FOR_EACH_PTR(arg);
 738
 739         arg_type = calloc(n_arg, sizeof(LLVMTypeRef));
 740
 741         int idx = 0;
 742         FOR_EACH_PTR(insn->arguments, arg) {
 743                 arg_type[idx++] = pseudo_type(fn, insn, arg);
 744         } END_FOR_EACH_PTR(arg);
 745
 746         func_type = LLVMFunctionType(ret_type, arg_type, n_arg,
 747                                      insn->fntype->variadic);
 748
 749         return func_type;
 750 }
 751
 752 static LLVMValueRef get_function(struct function *fn, struct instruction *insn)
 753 {
 754         struct symbol *sym = insn->func->sym;
 755         char buffer[256];
 756         LLVMValueRef func;
 757         struct llfunc *f;
 758
 759         if (sym->ident)
 760                 sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name);
 761         else
 762                 sprintf(buffer, "<anon sym %p>", sym);
 763
 764
 765         /* search for pre-built function type definition */
 766         FOR_EACH_PTR(mi.llfunc_list, f) {
 767                 if (!strcmp(f->name, buffer))
 768                         return f->func;         /* found match; return */
 769         } END_FOR_EACH_PTR(f);
 770
 771         /* build function type definition */
 772         LLVMTypeRef func_type = get_func_type(fn, insn);
 773
 774         func = LLVMAddFunction(fn->module, buffer, func_type);
 775
 776         /* store built function on list, for later referencing */
 777         f = calloc(1, sizeof(*f));
 778         strncpy(f->name, buffer, sizeof(f->name) - 1);
 779         f->func = func;
 780
 781         add_ptr_list(&mi.llfunc_list, f);
 782
 783         return func;
 784 }
 785
 786 static void output_op_call(struct function *fn, struct instruction *insn)
 787 {
 788         LLVMValueRef target, func;
 789         int n_arg = 0, i;
 790         struct pseudo *arg;
 791         LLVMValueRef *args;
 792
 793         FOR_EACH_PTR(insn->arguments, arg) {
 794                 n_arg++;
 795         } END_FOR_EACH_PTR(arg);
 796
 797         args = calloc(n_arg, sizeof(LLVMValueRef));
 798
 799         i = 0;
 800         FOR_EACH_PTR(insn->arguments, arg) {
 801                 args[i++] = pseudo_to_value(fn, insn, arg);
 802         } END_FOR_EACH_PTR(arg);
 803
 804         func = get_function(fn, insn);
 805         target = LLVMBuildCall(fn->builder, func, args, n_arg, "");
 806
 807         insn->target->priv = target;
 808 }
 809
 810 static void store_phi_fwd(struct function *fn, LLVMValueRef phi,
 811                           pseudo_t pseudo)
 812 {
 813         struct phi_fwd *fwd;
 814
 815         fwd = calloc(1, sizeof(*fwd));
 816         fwd->phi = phi;
 817         fwd->pseudo = pseudo;
 818
 819         /* append fwd ref to function-wide list */
 820         if (!fn->fwd_list)
 821                 fn->fwd_list = fwd;
 822         else {
 823                 struct phi_fwd *last = fn->fwd_list;
 824
 825                 while (last->next)
 826                         last = last->next;
 827                 last->next = fwd;
 828         }
 829 }
 830
 831 static void output_phi_fwd(struct function *fn, pseudo_t pseudo, LLVMValueRef v)
 832 {
 833         struct phi_fwd *fwd = fn->fwd_list;
 834
 835         while (fwd) {
 836                 struct phi_fwd *tmp;
 837
 838                 tmp = fwd;
 839                 fwd = fwd->next;
 840
 841                 if (tmp->pseudo == pseudo && !tmp->resolved) {
 842                         LLVMValueRef phi_vals[1];
 843                         LLVMBasicBlockRef phi_blks[1];
 844
 845                         phi_vals[0] = v;
 846                         phi_blks[0] = pseudo->def->bb->priv;
 847
 848                         LLVMAddIncoming(tmp->phi, phi_vals, phi_blks, 1);
 849
 850                         tmp->resolved = true;
 851                 }
 852         }
 853 }
 854
 855 static void output_op_phisrc(struct function *fn, struct instruction *insn)
 856 {
 857         LLVMValueRef v;
 858
 859         assert(insn->target->priv == NULL);
 860
 861         /* target = src */
 862         v = pseudo_to_value(fn, insn, insn->phi_src);
 863         insn->target->priv = v;
 864
 865         assert(insn->target->priv != NULL);
 866
 867         /* resolve forward references to this phi source, if present */
 868         output_phi_fwd(fn, insn->target, v);
 869 }
 870
 871 static void output_op_phi(struct function *fn, struct instruction *insn)
 872 {
 873         pseudo_t phi;
 874         LLVMValueRef target;
 875
 876         target = LLVMBuildPhi(fn->builder, insn_symbol_type(fn->module, insn),
 877                                 "phi");
 878         int pll = 0;
 879         FOR_EACH_PTR(insn->phi_list, phi) {
 880                 if (pseudo_to_value(fn, insn, phi))     /* skip VOID, fwd refs*/
 881                         pll++;
 882         } END_FOR_EACH_PTR(phi);
 883
 884         LLVMValueRef *phi_vals = calloc(pll, sizeof(LLVMValueRef));
 885         LLVMBasicBlockRef *phi_blks = calloc(pll, sizeof(LLVMBasicBlockRef));
 886
 887         int idx = 0;
 888         FOR_EACH_PTR(insn->phi_list, phi) {
 889                 LLVMValueRef v;
 890
 891                 v = pseudo_to_value(fn, insn, phi);
 892                 if (v) {                        /* skip VOID, fwd refs */
 893                         phi_vals[idx] = v;
 894                         phi_blks[idx] = phi->def->bb->priv;
 895                         idx++;
 896                 }
 897                 else if (phi->type == PSEUDO_PHI)       /* fwd ref */
 898                         store_phi_fwd(fn, target, phi);
 899         } END_FOR_EACH_PTR(phi);
 900
 901         LLVMAddIncoming(target, phi_vals, phi_blks, pll);
 902
 903         insn->target->priv = target;
 904 }
 905
 906 static void output_op_ptrcast(struct function *fn, struct instruction *insn)
 907 {
 908         LLVMValueRef src, target;
 909         char target_name[64];
 910
 911         src = insn->src->priv;
 912         if (!src)
 913                 src = pseudo_to_value(fn, insn, insn->src);
 914
 915         pseudo_name(insn->target, target_name);
 916
 917         assert(!symbol_is_fp_type(insn->type));
 918
 919         target = LLVMBuildBitCast(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
 920
 921         insn->target->priv = target;
 922 }
 923
 924 static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op)
 925 {
 926         LLVMValueRef src, target;
 927         char target_name[64];
 928
 929         src = insn->src->priv;
 930         if (!src)
 931                 src = pseudo_to_value(fn, insn, insn->src);
 932
 933         pseudo_name(insn->target, target_name);
 934
 935         assert(!symbol_is_fp_type(insn->type));
 936
 937         if (insn->size < LLVMGetIntTypeWidth(LLVMTypeOf(src)))
 938                 target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
 939         else
 940                 target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(fn->module, insn), target_name);
 941
 942         insn->target->priv = target;
 943 }
 944
 945 static void output_op_copy(struct function *fn, struct instruction *insn,
 946                            pseudo_t pseudo)
 947 {
 948         LLVMValueRef src, target;
 949         LLVMTypeRef const_type;
 950         char target_name[64];
 951
 952         pseudo_name(insn->target, target_name);
 953         src = pseudo_to_value(fn, insn, pseudo);
 954         const_type = insn_symbol_type(fn->module, insn);
 955
 956         /*
 957          * This is nothing more than 'target = src'
 958          *
 959          * TODO: find a better way to provide an identity function,
 960          * than using "X + 0" simply to produce a new LLVM pseudo
 961          */
 962
 963         if (symbol_is_fp_type(insn->type))
 964                 target = LLVMBuildFAdd(fn->builder, src,
 965                         LLVMConstReal(const_type, 0.0), target_name);
 966         else
 967                 target = LLVMBuildAdd(fn->builder, src,
 968                         LLVMConstInt(const_type, 0, 0), target_name);
 969
 970         insn->target->priv = target;
 971 }
 972
 973 static void output_insn(struct function *fn, struct instruction *insn)
 974 {
 975         switch (insn->opcode) {
 976         case OP_RET:
 977                 output_op_ret(fn, insn);
 978                 break;
 979         case OP_BR:
 980                 output_op_br(fn, insn);
 981                 break;
 982         case OP_SYMADDR:
 983                 assert(0);
 984                 break;
 985         case OP_SETVAL:
 986                 assert(0);
 987                 break;
 988         case OP_SWITCH:
 989                 output_op_switch(fn, insn);
 990                 break;
 991         case OP_COMPUTEDGOTO:
 992                 assert(0);
 993                 break;
 994         case OP_PHISOURCE:
 995                 output_op_phisrc(fn, insn);
 996                 break;
 997         case OP_PHI:
 998                 output_op_phi(fn, insn);
 999                 break;
1000         case OP_LOAD:
1001                 output_op_load(fn, insn);
1002                 break;
1003         case OP_LNOP:
1004                 assert(0);
1005                 break;
1006         case OP_STORE:
1007                 output_op_store(fn, insn);
1008                 break;
1009         case OP_SNOP:
1010                 assert(0);
1011                 break;
1012         case OP_INLINED_CALL:
1013                 assert(0);
1014                 break;
1015         case OP_CALL:
1016                 output_op_call(fn, insn);
1017                 break;
1018         case OP_CAST:
1019                 output_op_cast(fn, insn, LLVMZExt);
1020                 break;
1021         case OP_SCAST:
1022                 output_op_cast(fn, insn, LLVMSExt);
1023                 break;
1024         case OP_FPCAST:
1025                 assert(0);
1026                 break;
1027         case OP_PTRCAST:
1028                 output_op_ptrcast(fn, insn);
1029                 break;
1030         case OP_BINARY ... OP_BINARY_END:
1031         case OP_BINCMP ... OP_BINCMP_END:
1032                 output_op_binary(fn, insn);
1033                 break;
1034         case OP_SEL:
1035                 output_op_sel(fn, insn);
1036                 break;
1037         case OP_SLICE:
1038                 assert(0);
1039                 break;
1040         case OP_NOT: {
1041                 LLVMValueRef src, target;
1042                 char target_name[64];
1043
1044                 src = pseudo_to_value(fn, insn, insn->src);
1045
1046                 pseudo_name(insn->target, target_name);
1047
1048                 target = LLVMBuildNot(fn->builder, src, target_name);
1049
1050                 insn->target->priv = target;
1051                 break;
1052         }
1053         case OP_NEG:
1054                 assert(0);
1055                 break;
1056         case OP_CONTEXT:
1057                 assert(0);
1058                 break;
1059         case OP_RANGE:
1060                 assert(0);
1061                 break;
1062         case OP_NOP:
1063                 assert(0);
1064                 break;
1065         case OP_DEATHNOTE:
1066                 assert(0);
1067                 break;
1068         case OP_ASM:
1069                 assert(0);
1070                 break;
1071         case OP_COPY:
1072                 output_op_copy(fn, insn, insn->src);
1073                 break;
1074         default:
1075                 break;
1076         }
1077 }
1078
1079 static void output_bb(struct function *fn, struct basic_block *bb, unsigned long generation)
1080 {
1081         struct instruction *insn;
1082
1083         bb->generation = generation;
1084
1085         FOR_EACH_PTR(bb->insns, insn) {
1086                 if (!insn->bb)
1087                         continue;
1088
1089                 output_insn(fn, insn);
1090         }
1091         END_FOR_EACH_PTR(insn);
1092 }
1093
1094 #define MAX_ARGS        64
1095
1096 static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
1097 {
1098         unsigned long generation = ++bb_generation;
1099         struct symbol *sym = ep->name;
1100         struct symbol *base_type = sym->ctype.base_type;
1101         struct symbol *ret_type = sym->ctype.base_type->ctype.base_type;
1102         LLVMTypeRef arg_types[MAX_ARGS];
1103         LLVMTypeRef return_type;
1104         struct function function = { .module = module };
1105         struct basic_block *bb;
1106         struct symbol *arg;
1107         const char *name;
1108         int nr_args = 0;
1109         struct llfunc *f;
1110
1111         FOR_EACH_PTR(base_type->arguments, arg) {
1112                 struct symbol *arg_base_type = arg->ctype.base_type;
1113
1114                 arg_types[nr_args++] = symbol_type(module, arg_base_type);
1115         } END_FOR_EACH_PTR(arg);
1116
1117         name = show_ident(sym->ident);
1118
1119         return_type = symbol_type(module, ret_type);
1120
1121         function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0);
1122
1123         function.fn = LLVMAddFunction(module, name, function.type);
1124         LLVMSetFunctionCallConv(function.fn, LLVMCCallConv);
1125
1126         LLVMSetLinkage(function.fn, function_linkage(sym));
1127
1128         /* store built function on list, for later referencing */
1129         f = calloc(1, sizeof(*f));
1130         strncpy(f->name, name, sizeof(f->name) - 1);
1131         f->func = function.fn;
1132
1133         add_ptr_list(&mi.llfunc_list, f);
1134
1135         function.builder = LLVMCreateBuilder();
1136
1137         static int nr_bb;
1138
1139         FOR_EACH_PTR(ep->bbs, bb) {
1140                 if (bb->generation == generation)
1141                         continue;
1142
1143                 LLVMBasicBlockRef bbr;
1144                 char bbname[32];
1145
1146                 sprintf(bbname, "L%d", nr_bb++);
1147                 bbr = LLVMAppendBasicBlock(function.fn, bbname);
1148
1149                 bb->priv = bbr;
1150         }
1151         END_FOR_EACH_PTR(bb);
1152
1153         FOR_EACH_PTR(ep->bbs, bb) {
1154                 if (bb->generation == generation)
1155                         continue;
1156
1157                 LLVMPositionBuilderAtEnd(function.builder, bb->priv);
1158
1159                 output_bb(&function, bb, generation);
1160         }
1161         END_FOR_EACH_PTR(bb);
1162 }
1163
1164 static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym)
1165 {
1166         struct expression *initializer = sym->initializer;
1167         LLVMValueRef initial_value;
1168         LLVMValueRef data;
1169         const char *name;
1170
1171         if (initializer) {
1172                 switch (initializer->type) {
1173                 case EXPR_VALUE:
1174                         initial_value = LLVMConstInt(symbol_type(module, sym), initializer->value, 1);
1175                         break;
1176                 case EXPR_SYMBOL: {
1177                         struct symbol *sym = initializer->symbol;
1178
1179                         initial_value = LLVMGetNamedGlobal(module, show_ident(sym->ident));
1180                         if (!initial_value)
1181                                 initial_value = output_data(module, sym);
1182                         break;
1183                 }
1184                 default:
1185                         assert(0);
1186                 }
1187         } else {
1188                 LLVMTypeRef type = symbol_type(module, sym);
1189
1190                 initial_value = LLVMConstNull(type);
1191         }
1192
1193         name = show_ident(sym->ident);
1194
1195         data = LLVMAddGlobal(module, symbol_type(module, sym->ctype.base_type), name);
1196
1197         LLVMSetLinkage(data, data_linkage(sym));
1198
1199         if (!(sym->ctype.modifiers & MOD_EXTERN))
1200                 LLVMSetInitializer(data, initial_value);
1201
1202         return data;
1203 }
1204
1205 static int compile(LLVMModuleRef module, struct symbol_list *list)
1206 {
1207         struct symbol *sym;
1208
1209         FOR_EACH_PTR(list, sym) {
1210                 struct entrypoint *ep;
1211                 expand_symbol(sym);
1212                 ep = linearize_symbol(sym);
1213                 if (ep)
1214                         output_fn(module, ep);
1215                 else
1216                         output_data(module, sym);
1217         }
1218         END_FOR_EACH_PTR(sym);
1219
1220         return 0;
1221 }
1222
1223 int main(int argc, char **argv)
1224 {
1225         struct string_list * filelist = NULL;
1226         char *file;
1227
1228         LLVMModuleRef module = LLVMModuleCreateWithName("sparse");
1229
1230         compile(module, sparse_initialize(argc, argv, &filelist));
1231
1232         FOR_EACH_PTR_NOTAG(filelist, file) {
1233                 compile(module, sparse(file));
1234         } END_FOR_EACH_PTR_NOTAG(file);
1235
1236         LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0);
1237
1238         LLVMDisposeModule(module);
1239
1240         return 0;
1241 }