1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372 |
- /*
- * Example usage:
- * ./sparse-llvm hello.c | llc | as -o hello.o
- */
- #include <llvm-c/Core.h>
- #include <llvm-c/BitWriter.h>
- #include <llvm-c/Analysis.h>
- #include <llvm-c/Target.h>
- #include <stdbool.h>
- #include <stdio.h>
- #include <unistd.h>
- #include <string.h>
- #include <assert.h>
- #include "symbol.h"
- #include "expression.h"
- #include "linearize.h"
- #include "flow.h"
- struct function {
- LLVMBuilderRef builder;
- LLVMValueRef fn;
- LLVMModuleRef module;
- };
- static LLVMTypeRef symbol_type(struct symbol *sym);
- static LLVMTypeRef func_return_type(struct symbol *sym)
- {
- return symbol_type(sym->ctype.base_type);
- }
- static LLVMTypeRef sym_func_type(struct symbol *sym)
- {
- int n_arg = symbol_list_size(sym->arguments);
- LLVMTypeRef *arg_type = calloc(n_arg, sizeof(LLVMTypeRef));
- LLVMTypeRef ret_type = func_return_type(sym);
- struct symbol *arg;
- int idx = 0;
- FOR_EACH_PTR(sym->arguments, arg) {
- struct symbol *arg_sym = arg->ctype.base_type;
- arg_type[idx++] = symbol_type(arg_sym);
- } END_FOR_EACH_PTR(arg);
- return LLVMFunctionType(ret_type, arg_type, n_arg, sym->variadic);
- }
- static LLVMTypeRef sym_array_type(struct symbol *sym)
- {
- LLVMTypeRef elem_type;
- struct symbol *base_type;
- base_type = sym->ctype.base_type;
- /* empty struct is undefined [6.7.2.1(8)] */
- assert(base_type->bit_size > 0);
- elem_type = symbol_type(base_type);
- if (!elem_type)
- return NULL;
- return LLVMArrayType(elem_type, sym->bit_size / base_type->bit_size);
- }
- #define MAX_STRUCT_MEMBERS 64
- static LLVMTypeRef sym_struct_type(struct symbol *sym)
- {
- LLVMTypeRef elem_types[MAX_STRUCT_MEMBERS];
- struct symbol *member;
- char buffer[256];
- LLVMTypeRef ret;
- unsigned nr = 0;
- snprintf(buffer, sizeof(buffer), "struct.%s", sym->ident ? sym->ident->name : "anno");
- ret = LLVMStructCreateNamed(LLVMGetGlobalContext(), buffer);
- /* set ->aux to avoid recursion */
- sym->aux = ret;
- FOR_EACH_PTR(sym->symbol_list, member) {
- LLVMTypeRef member_type;
- assert(nr < MAX_STRUCT_MEMBERS);
- member_type = symbol_type(member);
- elem_types[nr++] = member_type;
- } END_FOR_EACH_PTR(member);
- LLVMStructSetBody(ret, elem_types, nr, 0 /* packed? */);
- return ret;
- }
- static LLVMTypeRef sym_union_type(struct symbol *sym)
- {
- LLVMTypeRef elements;
- unsigned union_size;
- /*
- * There's no union support in the LLVM API so we treat unions as
- * opaque structs. The downside is that we lose type information on the
- * members but as LLVM doesn't care, neither do we.
- */
- union_size = sym->bit_size / 8;
- elements = LLVMArrayType(LLVMInt8Type(), union_size);
- return LLVMStructType(&elements, 1, 0 /* packed? */);
- }
- static LLVMTypeRef sym_ptr_type(struct symbol *sym)
- {
- LLVMTypeRef type;
- /* 'void *' is treated like 'char *' */
- if (is_void_type(sym->ctype.base_type))
- type = LLVMInt8Type();
- else
- type = symbol_type(sym->ctype.base_type);
- return LLVMPointerType(type, 0);
- }
- static LLVMTypeRef sym_basetype_type(struct symbol *sym)
- {
- LLVMTypeRef ret = NULL;
- if (is_float_type(sym)) {
- switch (sym->bit_size) {
- case 32:
- ret = LLVMFloatType();
- break;
- case 64:
- ret = LLVMDoubleType();
- break;
- case 80:
- ret = LLVMX86FP80Type();
- break;
- default:
- die("invalid bit size %d for type %d", sym->bit_size, sym->type);
- break;
- }
- } else {
- switch (sym->bit_size) {
- case -1:
- ret = LLVMVoidType();
- break;
- case 1:
- ret = LLVMInt1Type();
- break;
- case 8:
- ret = LLVMInt8Type();
- break;
- case 16:
- ret = LLVMInt16Type();
- break;
- case 32:
- ret = LLVMInt32Type();
- break;
- case 64:
- ret = LLVMInt64Type();
- break;
- default:
- die("invalid bit size %d for type %d", sym->bit_size, sym->type);
- break;
- }
- }
- return ret;
- }
- static LLVMTypeRef symbol_type(struct symbol *sym)
- {
- LLVMTypeRef ret = NULL;
- /* don't cache the result for SYM_NODE */
- if (sym->type == SYM_NODE)
- return symbol_type(sym->ctype.base_type);
- if (sym->aux)
- return sym->aux;
- switch (sym->type) {
- case SYM_BITFIELD:
- ret = LLVMIntType(sym->bit_size);
- break;
- case SYM_RESTRICT:
- case SYM_ENUM:
- ret = symbol_type(sym->ctype.base_type);
- break;
- case SYM_BASETYPE:
- ret = sym_basetype_type(sym);
- break;
- case SYM_PTR:
- ret = sym_ptr_type(sym);
- break;
- case SYM_UNION:
- ret = sym_union_type(sym);
- break;
- case SYM_STRUCT:
- ret = sym_struct_type(sym);
- break;
- case SYM_ARRAY:
- ret = sym_array_type(sym);
- break;
- case SYM_FN:
- ret = sym_func_type(sym);
- break;
- default:
- assert(0);
- }
- /* cache the result */
- sym->aux = ret;
- return ret;
- }
- static LLVMTypeRef insn_symbol_type(struct instruction *insn)
- {
- if (insn->type)
- return symbol_type(insn->type);
- switch (insn->size) {
- case 8: return LLVMInt8Type();
- case 16: return LLVMInt16Type();
- case 32: return LLVMInt32Type();
- case 64: return LLVMInt64Type();
- default:
- die("invalid bit size %d", insn->size);
- break;
- }
- return NULL; /* not reached */
- }
- static LLVMLinkage data_linkage(struct symbol *sym)
- {
- if (sym->ctype.modifiers & MOD_STATIC)
- return LLVMPrivateLinkage;
- return LLVMExternalLinkage;
- }
- static LLVMLinkage function_linkage(struct symbol *sym)
- {
- if (sym->ctype.modifiers & MOD_STATIC)
- return LLVMInternalLinkage;
- return LLVMExternalLinkage;
- }
- #define MAX_PSEUDO_NAME 64
- static const char *pseudo_name(pseudo_t pseudo, char *buf)
- {
- switch (pseudo->type) {
- case PSEUDO_REG:
- snprintf(buf, MAX_PSEUDO_NAME, "R%d.", pseudo->nr);
- break;
- case PSEUDO_PHI:
- snprintf(buf, MAX_PSEUDO_NAME, "PHI%d.", pseudo->nr);
- break;
- case PSEUDO_SYM:
- case PSEUDO_VAL:
- case PSEUDO_ARG:
- case PSEUDO_VOID:
- buf[0] = '\0';
- break;
- case PSEUDO_UNDEF:
- assert(0);
- break;
- default:
- assert(0);
- }
- return buf;
- }
- static LLVMValueRef get_sym_value(LLVMModuleRef module, struct symbol *sym)
- {
- const char *name = show_ident(sym->ident);
- LLVMTypeRef type = symbol_type(sym);
- LLVMValueRef result = NULL;
- struct expression *expr;
- assert(sym->bb_target == NULL);
- expr = sym->initializer;
- if (expr && !sym->ident) {
- switch (expr->type) {
- case EXPR_STRING: {
- const char *s = expr->string->data;
- LLVMValueRef indices[] = { LLVMConstInt(LLVMInt64Type(), 0, 0), LLVMConstInt(LLVMInt64Type(), 0, 0) };
- LLVMValueRef data;
- data = LLVMAddGlobal(module, LLVMArrayType(LLVMInt8Type(), strlen(s) + 1), ".str");
- LLVMSetLinkage(data, LLVMPrivateLinkage);
- LLVMSetGlobalConstant(data, 1);
- LLVMSetInitializer(data, LLVMConstString(strdup(s), strlen(s) + 1, true));
- result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices));
- return result;
- }
- default:
- break;
- }
- }
- if (LLVMGetTypeKind(type) == LLVMFunctionTypeKind) {
- result = LLVMGetNamedFunction(module, name);
- if (!result)
- result = LLVMAddFunction(module, name, type);
- } else {
- result = LLVMGetNamedGlobal(module, name);
- if (!result)
- result = LLVMAddGlobal(module, type, name);
- }
- return result;
- }
- static LLVMValueRef constant_value(unsigned long long val, LLVMTypeRef dtype)
- {
- LLVMValueRef result;
- switch (LLVMGetTypeKind(dtype)) {
- case LLVMPointerTypeKind:
- if (val != 0) { // for example: ... = (void*) 0x123;
- LLVMTypeRef itype = LLVMIntType(bits_in_pointer);
- result = LLVMConstInt(itype, val, 1);
- result = LLVMConstIntToPtr(result, dtype);
- } else {
- result = LLVMConstPointerNull(dtype);
- }
- break;
- case LLVMIntegerTypeKind:
- result = LLVMConstInt(dtype, val, 1);
- break;
- case LLVMArrayTypeKind:
- case LLVMStructTypeKind:
- if (val != 0)
- return NULL;
- result = LLVMConstNull(dtype);
- break;
- default:
- return NULL;
- }
- return result;
- }
- static LLVMValueRef val_to_value(unsigned long long val, struct symbol *ctype)
- {
- LLVMValueRef result;
- LLVMTypeRef dtype;
- assert(ctype);
- dtype = symbol_type(ctype);
- result = constant_value(val, dtype);
- if (result)
- return result;
- sparse_error(ctype->pos, "no value possible for %s", show_typename(ctype));
- return LLVMGetUndef(symbol_type(ctype));
- }
- static LLVMValueRef pseudo_to_value(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
- {
- LLVMValueRef result = NULL;
- switch (pseudo->type) {
- case PSEUDO_REG:
- result = pseudo->priv;
- break;
- case PSEUDO_SYM:
- result = get_sym_value(fn->module, pseudo->sym);
- break;
- case PSEUDO_VAL:
- result = val_to_value(pseudo->value, ctype);
- break;
- case PSEUDO_ARG: {
- result = LLVMGetParam(fn->fn, pseudo->nr - 1);
- break;
- }
- case PSEUDO_PHI:
- result = pseudo->priv;
- break;
- case PSEUDO_VOID:
- result = NULL;
- break;
- case PSEUDO_UNDEF:
- result = LLVMGetUndef(symbol_type(ctype));
- break;
- default:
- assert(0);
- }
- return result;
- }
- static LLVMValueRef pseudo_to_rvalue(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
- {
- LLVMValueRef val = pseudo_to_value(fn, ctype, pseudo);
- LLVMTypeRef dtype = symbol_type(ctype);
- char name[MAX_PSEUDO_NAME];
- pseudo_name(pseudo, name);
- return LLVMBuildBitCast(fn->builder, val, dtype, name);
- }
- static LLVMValueRef value_to_ivalue(struct function *fn, struct symbol *ctype, LLVMValueRef val)
- {
- const char *name = LLVMGetValueName(val);
- LLVMTypeRef dtype = symbol_type(ctype);
- if (LLVMGetTypeKind(LLVMTypeOf(val)) == LLVMPointerTypeKind) {
- LLVMTypeRef dtype = LLVMIntType(bits_in_pointer);
- val = LLVMBuildPtrToInt(fn->builder, val, dtype, name);
- }
- if (ctype && is_int_type(ctype)) {
- val = LLVMBuildIntCast(fn->builder, val, dtype, name);
- }
- return val;
- }
- static LLVMValueRef value_to_pvalue(struct function *fn, struct symbol *ctype, LLVMValueRef val)
- {
- const char *name = LLVMGetValueName(val);
- LLVMTypeRef dtype = symbol_type(ctype);
- assert(is_ptr_type(ctype));
- switch (LLVMGetTypeKind(LLVMTypeOf(val))) {
- case LLVMIntegerTypeKind:
- val = LLVMBuildIntToPtr(fn->builder, val, dtype, name);
- break;
- case LLVMPointerTypeKind:
- val = LLVMBuildBitCast(fn->builder, val, dtype, name);
- break;
- default:
- break;
- }
- return val;
- }
- static LLVMValueRef adjust_type(struct function *fn, struct symbol *ctype, LLVMValueRef val)
- {
- if (is_int_type(ctype))
- return value_to_ivalue(fn, ctype, val);
- if (is_ptr_type(ctype))
- return value_to_pvalue(fn, ctype, val);
- return val;
- }
- /*
- * Get the LLVMValue corresponding to the pseudo
- * and force the type corresponding to ctype.
- */
- static LLVMValueRef get_operand(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
- {
- LLVMValueRef target = pseudo_to_value(fn, ctype, pseudo);
- return adjust_type(fn, ctype, target);
- }
- /*
- * Get the LLVMValue corresponding to the pseudo
- * and force the type corresponding to ctype but
- * map all pointers to intptr_t.
- */
- static LLVMValueRef get_ioperand(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
- {
- LLVMValueRef target = pseudo_to_value(fn, ctype, pseudo);
- return value_to_ivalue(fn, ctype, target);
- }
- static LLVMValueRef calc_gep(LLVMBuilderRef builder, LLVMValueRef base, LLVMValueRef off)
- {
- LLVMTypeRef type = LLVMTypeOf(base);
- unsigned int as = LLVMGetPointerAddressSpace(type);
- LLVMTypeRef bytep = LLVMPointerType(LLVMInt8Type(), as);
- LLVMValueRef addr;
- const char *name = LLVMGetValueName(off);
- /* convert base to char* type */
- base = LLVMBuildPointerCast(builder, base, bytep, name);
- /* addr = base + off */
- addr = LLVMBuildInBoundsGEP(builder, base, &off, 1, name);
- /* convert back to the actual pointer type */
- addr = LLVMBuildPointerCast(builder, addr, type, name);
- return addr;
- }
- static LLVMRealPredicate translate_fop(int opcode)
- {
- static const LLVMRealPredicate trans_tbl[] = {
- [OP_FCMP_ORD] = LLVMRealORD,
- [OP_FCMP_OEQ] = LLVMRealOEQ,
- [OP_FCMP_ONE] = LLVMRealONE,
- [OP_FCMP_OLE] = LLVMRealOLE,
- [OP_FCMP_OGE] = LLVMRealOGE,
- [OP_FCMP_OLT] = LLVMRealOLT,
- [OP_FCMP_OGT] = LLVMRealOGT,
- [OP_FCMP_UEQ] = LLVMRealUEQ,
- [OP_FCMP_UNE] = LLVMRealUNE,
- [OP_FCMP_ULE] = LLVMRealULE,
- [OP_FCMP_UGE] = LLVMRealUGE,
- [OP_FCMP_ULT] = LLVMRealULT,
- [OP_FCMP_UGT] = LLVMRealUGT,
- [OP_FCMP_UNO] = LLVMRealUNO,
- };
- return trans_tbl[opcode];
- }
- static LLVMIntPredicate translate_op(int opcode)
- {
- static const LLVMIntPredicate trans_tbl[] = {
- [OP_SET_EQ] = LLVMIntEQ,
- [OP_SET_NE] = LLVMIntNE,
- [OP_SET_LE] = LLVMIntSLE,
- [OP_SET_GE] = LLVMIntSGE,
- [OP_SET_LT] = LLVMIntSLT,
- [OP_SET_GT] = LLVMIntSGT,
- [OP_SET_B] = LLVMIntULT,
- [OP_SET_A] = LLVMIntUGT,
- [OP_SET_BE] = LLVMIntULE,
- [OP_SET_AE] = LLVMIntUGE,
- };
- return trans_tbl[opcode];
- }
- static void output_op_binary(struct function *fn, struct instruction *insn)
- {
- LLVMValueRef lhs, rhs, target;
- char target_name[64];
- lhs = get_ioperand(fn, insn->type, insn->src1);
- rhs = get_ioperand(fn, insn->type, insn->src2);
- pseudo_name(insn->target, target_name);
- switch (insn->opcode) {
- /* Binary */
- case OP_ADD:
- target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name);
- break;
- case OP_SUB:
- target = LLVMBuildSub(fn->builder, lhs, rhs, target_name);
- break;
- case OP_MUL:
- target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
- break;
- case OP_DIVU:
- target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name);
- break;
- case OP_DIVS:
- assert(!is_float_type(insn->type));
- target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name);
- break;
- case OP_MODU:
- assert(!is_float_type(insn->type));
- target = LLVMBuildURem(fn->builder, lhs, rhs, target_name);
- break;
- case OP_MODS:
- assert(!is_float_type(insn->type));
- target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name);
- break;
- case OP_SHL:
- assert(!is_float_type(insn->type));
- target = LLVMBuildShl(fn->builder, lhs, rhs, target_name);
- break;
- case OP_LSR:
- assert(!is_float_type(insn->type));
- target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name);
- break;
- case OP_ASR:
- assert(!is_float_type(insn->type));
- target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name);
- break;
- /* floating-point */
- case OP_FADD:
- target = LLVMBuildFAdd(fn->builder, lhs, rhs, target_name);
- break;
- case OP_FSUB:
- target = LLVMBuildFSub(fn->builder, lhs, rhs, target_name);
- break;
- case OP_FMUL:
- target = LLVMBuildFMul(fn->builder, lhs, rhs, target_name);
- break;
- case OP_FDIV:
- target = LLVMBuildFDiv(fn->builder, lhs, rhs, target_name);
- break;
-
- /* Logical */
- case OP_AND:
- assert(!is_float_type(insn->type));
- target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name);
- break;
- case OP_OR:
- assert(!is_float_type(insn->type));
- target = LLVMBuildOr(fn->builder, lhs, rhs, target_name);
- break;
- case OP_XOR:
- assert(!is_float_type(insn->type));
- target = LLVMBuildXor(fn->builder, lhs, rhs, target_name);
- break;
- default:
- assert(0);
- break;
- }
- target = adjust_type(fn, insn->type, target);
- insn->target->priv = target;
- }
- static void output_op_compare(struct function *fn, struct instruction *insn)
- {
- LLVMValueRef lhs, rhs, target;
- char target_name[64];
- lhs = pseudo_to_value(fn, NULL, insn->src1);
- if (insn->src2->type == PSEUDO_VAL)
- rhs = constant_value(insn->src2->value, LLVMTypeOf(lhs));
- else
- rhs = pseudo_to_value(fn, NULL, insn->src2);
- if (!rhs)
- rhs = LLVMGetUndef(symbol_type(insn->type));
- pseudo_name(insn->target, target_name);
- LLVMTypeRef dst_type = insn_symbol_type(insn);
- switch (LLVMGetTypeKind(LLVMTypeOf(lhs))) {
- case LLVMPointerTypeKind:
- lhs = value_to_pvalue(fn, &ptr_ctype, lhs);
- rhs = value_to_pvalue(fn, &ptr_ctype, rhs);
- /* fall through */
- case LLVMIntegerTypeKind: {
- LLVMIntPredicate op = translate_op(insn->opcode);
- if (LLVMGetTypeKind(LLVMTypeOf(rhs)) == LLVMPointerTypeKind) {
- LLVMTypeRef ltype = LLVMTypeOf(lhs);
- rhs = LLVMBuildPtrToInt(fn->builder, rhs, ltype, "");
- }
- target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name);
- break;
- }
- case LLVMHalfTypeKind:
- case LLVMFloatTypeKind:
- case LLVMDoubleTypeKind:
- case LLVMX86_FP80TypeKind:
- case LLVMFP128TypeKind:
- case LLVMPPC_FP128TypeKind: {
- LLVMRealPredicate op = translate_fop(insn->opcode);
- target = LLVMBuildFCmp(fn->builder, op, lhs, rhs, target_name);
- break;
- }
- default:
- assert(0);
- }
- target = LLVMBuildZExt(fn->builder, target, dst_type, target_name);
- insn->target->priv = target;
- }
- static void output_op_ret(struct function *fn, struct instruction *insn)
- {
- pseudo_t pseudo = insn->src;
- if (pseudo && pseudo != VOID) {
- LLVMValueRef result = get_operand(fn, insn->type, pseudo);
- LLVMBuildRet(fn->builder, result);
- } else
- LLVMBuildRetVoid(fn->builder);
- }
- static LLVMValueRef calc_memop_addr(struct function *fn, struct instruction *insn)
- {
- LLVMTypeRef int_type, addr_type;
- LLVMValueRef src, off, addr;
- unsigned int as;
- /* int type large enough to hold a pointer */
- int_type = LLVMIntType(bits_in_pointer);
- off = LLVMConstInt(int_type, insn->offset, 0);
- /* convert src to the effective pointer type */
- src = pseudo_to_value(fn, insn->type, insn->src);
- as = LLVMGetPointerAddressSpace(LLVMTypeOf(src));
- addr_type = LLVMPointerType(insn_symbol_type(insn), as);
- src = LLVMBuildPointerCast(fn->builder, src, addr_type, LLVMGetValueName(src));
- /* addr = src + off */
- addr = calc_gep(fn->builder, src, off);
- return addr;
- }
- static void output_op_load(struct function *fn, struct instruction *insn)
- {
- LLVMValueRef addr, target;
- char name[MAX_PSEUDO_NAME];
- addr = calc_memop_addr(fn, insn);
- /* perform load */
- pseudo_name(insn->target, name);
- target = LLVMBuildLoad(fn->builder, addr, name);
- insn->target->priv = target;
- }
- static void output_op_store(struct function *fn, struct instruction *insn)
- {
- LLVMValueRef addr, target_in;
- addr = calc_memop_addr(fn, insn);
- target_in = pseudo_to_rvalue(fn, insn->type, insn->target);
- /* perform store */
- LLVMBuildStore(fn->builder, target_in, addr);
- }
- static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
- {
- if (LLVMTypeOf(value) != LLVMInt1Type())
- value = LLVMBuildIsNotNull(fn->builder, value, LLVMGetValueName(value));
- return value;
- }
- static void output_op_cbr(struct function *fn, struct instruction *br)
- {
- LLVMValueRef cond = bool_value(fn,
- pseudo_to_value(fn, NULL, br->cond));
- LLVMBuildCondBr(fn->builder, cond,
- br->bb_true->priv,
- br->bb_false->priv);
- }
- static void output_op_br(struct function *fn, struct instruction *br)
- {
- LLVMBuildBr(fn->builder, br->bb_true->priv);
- }
- static void output_op_sel(struct function *fn, struct instruction *insn)
- {
- LLVMValueRef target, src1, src2, src3;
- char name[MAX_PSEUDO_NAME];
- src1 = bool_value(fn, pseudo_to_value(fn, NULL, insn->src1));
- src2 = get_operand(fn, insn->type, insn->src2);
- src3 = get_operand(fn, insn->type, insn->src3);
- pseudo_name(insn->target, name);
- target = LLVMBuildSelect(fn->builder, src1, src2, src3, name);
- insn->target->priv = adjust_type(fn, insn->type, target);
- }
- static void output_op_switch(struct function *fn, struct instruction *insn)
- {
- LLVMValueRef sw_val, target;
- struct basic_block *def = NULL;
- struct multijmp *jmp;
- int n_jmp = 0;
- FOR_EACH_PTR(insn->multijmp_list, jmp) {
- if (jmp->begin <= jmp->end) {
- n_jmp += (jmp->end - jmp->begin) + 1;
- } else /* default case */
- def = jmp->target;
- } END_FOR_EACH_PTR(jmp);
- sw_val = get_ioperand(fn, insn->type, insn->cond);
- target = LLVMBuildSwitch(fn->builder, sw_val,
- def ? def->priv : NULL, n_jmp);
- FOR_EACH_PTR(insn->multijmp_list, jmp) {
- long long val;
- for (val = jmp->begin; val <= jmp->end; val++) {
- LLVMValueRef Val = val_to_value(val, insn->type);
- LLVMAddCase(target, Val, jmp->target->priv);
- }
- } END_FOR_EACH_PTR(jmp);
- }
- static void output_op_call(struct function *fn, struct instruction *insn)
- {
- LLVMValueRef target, func;
- struct symbol *ctype;
- int n_arg = 0, i;
- struct pseudo *arg;
- LLVMValueRef *args;
- char name[64];
- n_arg = pseudo_list_size(insn->arguments);
- args = calloc(n_arg, sizeof(LLVMValueRef));
- PREPARE_PTR_LIST(insn->fntypes, ctype);
- if (insn->func->type == PSEUDO_REG || insn->func->type == PSEUDO_PHI)
- func = get_operand(fn, ctype, insn->func);
- else
- func = pseudo_to_value(fn, ctype, insn->func);
- i = 0;
- FOR_EACH_PTR(insn->arguments, arg) {
- NEXT_PTR_LIST(ctype);
- args[i++] = pseudo_to_rvalue(fn, ctype, arg);
- } END_FOR_EACH_PTR(arg);
- FINISH_PTR_LIST(ctype);
- pseudo_name(insn->target, name);
- target = LLVMBuildCall(fn->builder, func, args, n_arg, name);
- insn->target->priv = target;
- }
- static void output_op_phisrc(struct function *fn, struct instruction *insn)
- {
- LLVMValueRef v;
- struct instruction *phi;
- assert(insn->target->priv == NULL);
- /* target = src */
- v = get_operand(fn, insn->type, insn->phi_src);
- FOR_EACH_PTR(insn->phi_users, phi) {
- LLVMValueRef load, ptr;
- assert(phi->opcode == OP_PHI);
- /* phi must be load from alloca */
- load = phi->target->priv;
- assert(LLVMGetInstructionOpcode(load) == LLVMLoad);
- ptr = LLVMGetOperand(load, 0);
- /* store v to alloca */
- LLVMBuildStore(fn->builder, v, ptr);
- } END_FOR_EACH_PTR(phi);
- }
- static void output_op_phi(struct function *fn, struct instruction *insn)
- {
- LLVMValueRef load = insn->target->priv;
- /* forward load */
- assert(LLVMGetInstructionOpcode(load) == LLVMLoad);
- /* forward load has no parent block */
- assert(!LLVMGetInstructionParent(load));
- /* finalize load in current block */
- LLVMInsertIntoBuilder(fn->builder, load);
- }
- static void output_op_ptrcast(struct function *fn, struct instruction *insn)
- {
- LLVMValueRef src, target;
- LLVMTypeRef dtype;
- struct symbol *otype = insn->orig_type;
- LLVMOpcode op;
- char target_name[64];
- src = get_operand(fn, otype, insn->src);
- pseudo_name(insn->target, target_name);
- dtype = symbol_type(insn->type);
- switch (insn->opcode) {
- case OP_UTPTR:
- case OP_SEXT: // FIXME
- assert(is_int_type(otype));
- assert(is_ptr_type(insn->type));
- op = LLVMIntToPtr;
- break;
- case OP_PTRTU:
- assert(is_ptr_type(otype));
- assert(is_int_type(insn->type));
- op = LLVMPtrToInt;
- break;
- case OP_PTRCAST:
- case OP_ZEXT: // FIXME
- assert(is_ptr_type(otype));
- assert(is_ptr_type(insn->type));
- op = LLVMBitCast;
- break;
- default:
- assert(0);
- }
- target = LLVMBuildCast(fn->builder, op, src, dtype, target_name);
- insn->target->priv = target;
- }
- static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op)
- {
- LLVMValueRef src, target;
- LLVMTypeRef dtype;
- struct symbol *otype = insn->orig_type;
- char target_name[64];
- if (is_ptr_type(insn->type)) // cast to void* is OP_CAST ...
- return output_op_ptrcast(fn, insn);
- assert(is_int_type(insn->type));
- src = get_operand(fn, otype, insn->src);
- pseudo_name(insn->target, target_name);
- dtype = symbol_type(insn->type);
- if (is_ptr_type(otype)) {
- op = LLVMPtrToInt;
- } else if (is_float_type(otype)) {
- assert(op == LLVMFPToUI || op == LLVMFPToSI);
- } else if (is_int_type(otype)) {
- unsigned int width = otype->bit_size;
- if (insn->size < width)
- op = LLVMTrunc;
- else if (insn->size == width)
- op = LLVMBitCast;
- } else {
- assert(0);
- }
- target = LLVMBuildCast(fn->builder, op, src, dtype, target_name);
- insn->target->priv = target;
- }
- static void output_op_fpcast(struct function *fn, struct instruction *insn)
- {
- LLVMTypeRef dtype = symbol_type(insn->type);
- LLVMValueRef src, target;
- struct symbol *otype = insn->orig_type;
- char name[64];
- assert(is_float_type(insn->type));
- pseudo_name(insn->target, name);
- src = get_operand(fn, otype, insn->src);
- switch (insn->opcode) {
- case OP_FCVTF:
- target = LLVMBuildFPCast(fn->builder, src, dtype, name);
- break;
- case OP_SCVTF:
- target = LLVMBuildSIToFP(fn->builder, src, dtype, name);
- break;
- case OP_UCVTF:
- target = LLVMBuildUIToFP(fn->builder, src, dtype, name);
- break;
- default:
- assert(0);
- }
- insn->target->priv = target;
- }
- static void output_op_setval(struct function *fn, struct instruction *insn)
- {
- struct expression *val = insn->val;
- LLVMValueRef target;
- switch (val->type) {
- case EXPR_LABEL:
- target = LLVMBlockAddress(fn->fn, val->symbol->bb_target->priv);
- break;
- default:
- assert(0);
- }
- insn->target->priv = target;
- }
- static void output_op_setfval(struct function *fn, struct instruction *insn)
- {
- LLVMTypeRef dtype = symbol_type(insn->type);
- LLVMValueRef target;
- target = LLVMConstReal(dtype, insn->fvalue);
- insn->target->priv = target;
- }
- static void output_insn(struct function *fn, struct instruction *insn)
- {
- switch (insn->opcode) {
- case OP_RET:
- output_op_ret(fn, insn);
- break;
- case OP_BR:
- output_op_br(fn, insn);
- break;
- case OP_CBR:
- output_op_cbr(fn, insn);
- break;
- case OP_SYMADDR:
- assert(0);
- break;
- case OP_SETVAL:
- output_op_setval(fn, insn);
- break;
- case OP_SETFVAL:
- output_op_setfval(fn, insn);
- break;
- case OP_SWITCH:
- output_op_switch(fn, insn);
- break;
- case OP_COMPUTEDGOTO:
- assert(0);
- break;
- case OP_PHISOURCE:
- output_op_phisrc(fn, insn);
- break;
- case OP_PHI:
- output_op_phi(fn, insn);
- break;
- case OP_LOAD:
- output_op_load(fn, insn);
- break;
- case OP_STORE:
- output_op_store(fn, insn);
- break;
- case OP_INLINED_CALL:
- break;
- case OP_CALL:
- output_op_call(fn, insn);
- break;
- case OP_ZEXT:
- output_op_cast(fn, insn, LLVMZExt);
- break;
- case OP_SEXT:
- output_op_cast(fn, insn, LLVMSExt);
- break;
- case OP_TRUNC:
- output_op_cast(fn, insn, LLVMTrunc);
- break;
- case OP_FCVTU:
- output_op_cast(fn, insn, LLVMFPToUI);
- break;
- case OP_FCVTS:
- output_op_cast(fn, insn, LLVMFPToSI);
- break;
- case OP_UCVTF: case OP_SCVTF:
- case OP_FCVTF:
- output_op_fpcast(fn, insn);
- break;
- case OP_UTPTR:
- case OP_PTRTU:
- case OP_PTRCAST:
- output_op_ptrcast(fn, insn);
- break;
- case OP_BINARY ... OP_BINARY_END:
- output_op_binary(fn, insn);
- break;
- case OP_FPCMP ... OP_BINCMP_END:
- output_op_compare(fn, insn);
- break;
- case OP_SEL:
- output_op_sel(fn, insn);
- break;
- case OP_SLICE:
- assert(0);
- break;
- case OP_NOT: {
- LLVMValueRef src, target;
- char target_name[64];
- src = pseudo_to_value(fn, insn->type, insn->src);
- pseudo_name(insn->target, target_name);
- target = LLVMBuildNot(fn->builder, src, target_name);
- insn->target->priv = target;
- break;
- }
- case OP_FNEG:
- case OP_NEG: {
- LLVMValueRef src, target;
- char target_name[64];
- src = pseudo_to_value(fn, insn->type, insn->src);
- pseudo_name(insn->target, target_name);
- if (insn->opcode == OP_FNEG)
- target = LLVMBuildFNeg(fn->builder, src, target_name);
- else
- target = LLVMBuildNeg(fn->builder, src, target_name);
- insn->target->priv = target;
- break;
- }
- case OP_CONTEXT:
- assert(0);
- break;
- case OP_RANGE:
- assert(0);
- break;
- case OP_NOP:
- assert(0);
- break;
- case OP_DEATHNOTE:
- break;
- case OP_ASM:
- assert(0);
- break;
- case OP_COPY:
- assert(0);
- break;
- default:
- break;
- }
- }
- static void output_bb(struct function *fn, struct basic_block *bb)
- {
- struct instruction *insn;
- FOR_EACH_PTR(bb->insns, insn) {
- if (!insn->bb)
- continue;
- output_insn(fn, insn);
- }
- END_FOR_EACH_PTR(insn);
- }
- #define MAX_ARGS 64
- static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
- {
- struct symbol *sym = ep->name;
- struct symbol *base_type = sym->ctype.base_type;
- struct function function = { .module = module };
- struct basic_block *bb;
- int nr_args = 0;
- int i;
- function.fn = get_sym_value(module, sym);
- LLVMSetFunctionCallConv(function.fn, LLVMCCallConv);
- LLVMSetLinkage(function.fn, function_linkage(sym));
- function.builder = LLVMCreateBuilder();
- /* give a name to each argument */
- nr_args = symbol_list_size(base_type->arguments);
- for (i = 0; i < nr_args; i++) {
- char name[MAX_PSEUDO_NAME];
- LLVMValueRef arg;
- arg = LLVMGetParam(function.fn, i);
- snprintf(name, sizeof(name), "ARG%d.", i+1);
- LLVMSetValueName(arg, name);
- }
- /* create the BBs */
- FOR_EACH_PTR(ep->bbs, bb) {
- static int nr_bb;
- LLVMBasicBlockRef bbr;
- char bbname[32];
- struct instruction *insn;
- sprintf(bbname, "L%d", nr_bb++);
- bbr = LLVMAppendBasicBlock(function.fn, bbname);
- bb->priv = bbr;
- /* allocate alloca for each phi */
- FOR_EACH_PTR(bb->insns, insn) {
- LLVMBasicBlockRef entrybbr;
- LLVMTypeRef phi_type;
- LLVMValueRef ptr;
- if (!insn->bb || insn->opcode != OP_PHI)
- continue;
- /* insert alloca into entry block */
- entrybbr = LLVMGetEntryBasicBlock(function.fn);
- LLVMPositionBuilderAtEnd(function.builder, entrybbr);
- phi_type = insn_symbol_type(insn);
- ptr = LLVMBuildAlloca(function.builder, phi_type, "");
- /* emit forward load for phi */
- LLVMClearInsertionPosition(function.builder);
- insn->target->priv = LLVMBuildLoad(function.builder, ptr, "phi");
- } END_FOR_EACH_PTR(insn);
- }
- END_FOR_EACH_PTR(bb);
- FOR_EACH_PTR(ep->bbs, bb) {
- LLVMPositionBuilderAtEnd(function.builder, bb->priv);
- output_bb(&function, bb);
- }
- END_FOR_EACH_PTR(bb);
- }
- static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym)
- {
- struct expression *initializer = sym->initializer;
- LLVMValueRef initial_value;
- LLVMValueRef data;
- const char *name;
- if (initializer) {
- switch (initializer->type) {
- case EXPR_VALUE:
- initial_value = LLVMConstInt(symbol_type(sym), initializer->value, 1);
- break;
- case EXPR_FVALUE:
- initial_value = LLVMConstReal(symbol_type(sym), initializer->fvalue);
- break;
- case EXPR_SYMBOL: {
- struct symbol *sym = initializer->symbol;
- initial_value = LLVMGetNamedGlobal(module, show_ident(sym->ident));
- if (!initial_value)
- initial_value = output_data(module, sym);
- break;
- }
- case EXPR_STRING: {
- const char *s = initializer->string->data;
- initial_value = LLVMConstString(strdup(s), strlen(s) + 1, true);
- break;
- }
- default:
- warning(initializer->pos, "can't initialize type: %s", show_typename(sym));
- initial_value = NULL;
- break;
- }
- } else {
- LLVMTypeRef type = symbol_type(sym);
- initial_value = LLVMConstNull(type);
- }
- if (!initial_value)
- return NULL;
- name = sym->ident ? show_ident(sym->ident) : "" ;
- data = LLVMAddGlobal(module, LLVMTypeOf(initial_value), name);
- LLVMSetLinkage(data, data_linkage(sym));
- if (sym->ctype.modifiers & MOD_CONST)
- LLVMSetGlobalConstant(data, 1);
- if (sym->ctype.modifiers & MOD_TLS)
- LLVMSetThreadLocal(data, 1);
- if (sym->ctype.alignment)
- LLVMSetAlignment(data, sym->ctype.alignment);
- if (!(sym->ctype.modifiers & MOD_EXTERN))
- LLVMSetInitializer(data, initial_value);
- return data;
- }
- static int is_prototype(struct symbol *sym)
- {
- if (sym->type == SYM_NODE)
- sym = sym->ctype.base_type;
- return sym && sym->type == SYM_FN && !sym->stmt;
- }
- static int compile(LLVMModuleRef module, struct symbol_list *list)
- {
- struct symbol *sym;
- FOR_EACH_PTR(list, sym) {
- struct entrypoint *ep;
- expand_symbol(sym);
- if (is_prototype(sym)) {
- // this will do the LLVMAddFunction() we want
- get_sym_value(module, sym);
- continue;
- }
- ep = linearize_symbol(sym);
- if (ep)
- output_fn(module, ep);
- else
- output_data(module, sym);
- }
- END_FOR_EACH_PTR(sym);
- return 0;
- }
- #ifndef LLVM_DEFAULT_TARGET_TRIPLE
- #define LLVM_DEFAULT_TARGET_TRIPLE LLVM_HOSTTRIPLE
- #endif
- #define X86_LINUX_LAYOUT \
- "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-" \
- "i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-" \
- "a0:0:64-f80:32:32-n8:16:32-S128"
- #define X86_64_LINUX_LAYOUT \
- "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-" \
- "i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-" \
- "a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
- static void set_target(LLVMModuleRef module)
- {
- char target[] = LLVM_DEFAULT_TARGET_TRIPLE;
- const char *arch, *vendor, *os, *env, *layout = NULL;
- char triple[256];
- arch = strtok(target, "-");
- vendor = strtok(NULL, "-");
- os = strtok(NULL, "-");
- env = strtok(NULL, "-");
- if (!os)
- return;
- if (!env)
- env = "unknown";
- if (!strcmp(arch, "x86_64") && !strcmp(os, "linux")) {
- if (arch_m64) {
- layout = X86_64_LINUX_LAYOUT;
- } else {
- arch = "i386";
- layout = X86_LINUX_LAYOUT;
- }
- }
- /* unsupported target */
- if (!layout)
- return;
- snprintf(triple, sizeof(triple), "%s-%s-%s-%s", arch, vendor, os, env);
- LLVMSetTarget(module, triple);
- LLVMSetDataLayout(module, layout);
- }
- int main(int argc, char **argv)
- {
- struct string_list *filelist = NULL;
- struct symbol_list *symlist;
- LLVMModuleRef module;
- char *file;
- symlist = sparse_initialize(argc, argv, &filelist);
- module = LLVMModuleCreateWithName("sparse");
- set_target(module);
- compile(module, symlist);
- /* need ->phi_users */
- dbg_dead = 1;
- FOR_EACH_PTR(filelist, file) {
- symlist = sparse(file);
- if (die_if_error)
- return 1;
- compile(module, symlist);
- } END_FOR_EACH_PTR(file);
- LLVMVerifyModule(module, LLVMPrintMessageAction, NULL);
- LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0);
- LLVMDisposeModule(module);
- report_stats();
- return 0;
- }
|