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