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