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