3 * ./sparse-llvm hello.c | llc | as -o hello.o
6 #include <llvm-c/Core.h>
7 #include <llvm-c/BitWriter.h>
16 #include "expression.h"
17 #include "linearize.h"
21 LLVMBuilderRef builder
;
27 static inline bool symbol_is_fp_type(struct symbol
*sym
)
29 return sym
->ctype
.base_type
== &fp_type
;
32 static LLVMTypeRef
symbol_type(struct symbol
*sym
)
34 LLVMTypeRef ret
= NULL
;
36 if (symbol_is_fp_type(sym
)) {
37 switch (sym
->bit_size
) {
39 ret
= LLVMFloatType();
42 ret
= LLVMDoubleType();
45 die("invalid bit size %d for type %d", sym
->bit_size
, sym
->type
);
49 switch (sym
->bit_size
) {
57 ret
= LLVMInt16Type();
60 ret
= LLVMInt32Type();
63 ret
= LLVMInt64Type();
66 die("invalid bit size %d for type %d", sym
->bit_size
, sym
->type
);
74 static LLVMLinkage
data_linkage(struct symbol
*sym
)
76 if (sym
->ctype
.modifiers
& MOD_STATIC
)
77 return LLVMPrivateLinkage
;
79 return LLVMExternalLinkage
;
82 static LLVMLinkage
function_linkage(struct symbol
*sym
)
84 if (sym
->ctype
.modifiers
& MOD_STATIC
)
85 return LLVMInternalLinkage
;
87 return LLVMExternalLinkage
;
90 #define MAX_PSEUDO_NAME 64
92 static void pseudo_name(pseudo_t pseudo
, char *buf
)
94 switch (pseudo
->type
) {
96 snprintf(buf
, MAX_PSEUDO_NAME
, "R%d", pseudo
->nr
);
109 snprintf(buf
, MAX_PSEUDO_NAME
, "PHI%d", pseudo
->nr
);
116 static LLVMValueRef
pseudo_to_value(struct function
*fn
, pseudo_t pseudo
)
118 LLVMValueRef result
= NULL
;
120 switch (pseudo
->type
) {
122 result
= pseudo
->priv
;
125 struct symbol
*sym
= pseudo
->sym
;
126 struct expression
*expr
;
128 assert(sym
->bb_target
== NULL
);
129 assert(sym
->ident
== NULL
);
131 expr
= sym
->initializer
;
133 switch (expr
->type
) {
135 const char *s
= expr
->string
->data
;
136 LLVMValueRef indices
[] = { LLVMConstInt(LLVMInt64Type(), 0, 0), LLVMConstInt(LLVMInt64Type(), 0, 0) };
139 data
= LLVMAddGlobal(fn
->module
, LLVMArrayType(LLVMInt8Type(), strlen(s
) + 1), ".str");
140 LLVMSetLinkage(data
, LLVMPrivateLinkage
);
141 LLVMSetGlobalConstant(data
, 1);
142 LLVMSetInitializer(data
, LLVMConstString(strdup(s
), strlen(s
) + 1, true));
144 result
= LLVMConstGEP(data
, indices
, ARRAY_SIZE(indices
));
154 result
= LLVMConstInt(LLVMGetReturnType(fn
->type
), pseudo
->value
, 1);
157 result
= LLVMGetParam(fn
->fn
, pseudo
->nr
- 1);
161 result
= pseudo
->priv
;
173 static LLVMTypeRef
pseudo_type(struct function
*fn
, pseudo_t pseudo
)
176 LLVMTypeRef result
= NULL
;
180 return LLVMTypeOf(v
);
183 switch (pseudo
->type
) {
185 result
= symbol_type(pseudo
->def
->type
);
188 struct symbol
*sym
= pseudo
->sym
;
189 struct expression
*expr
;
191 assert(sym
->bb_target
== NULL
);
192 assert(sym
->ident
== NULL
);
194 expr
= sym
->initializer
;
196 switch (expr
->type
) {
198 result
= LLVMPointerType(LLVMInt8Type(), 0);
217 result
= LLVMVoidType();
226 static void output_op_binary(struct function
*fn
, struct instruction
*insn
)
228 LLVMValueRef lhs
, rhs
, target
;
229 char target_name
[64];
231 lhs
= pseudo_to_value(fn
, insn
->src1
);
233 rhs
= pseudo_to_value(fn
, insn
->src2
);
235 pseudo_name(insn
->target
, target_name
);
237 switch (insn
->opcode
) {
240 if (symbol_is_fp_type(insn
->type
))
241 target
= LLVMBuildFAdd(fn
->builder
, lhs
, rhs
, target_name
);
243 target
= LLVMBuildAdd(fn
->builder
, lhs
, rhs
, target_name
);
246 if (symbol_is_fp_type(insn
->type
))
247 target
= LLVMBuildFSub(fn
->builder
, lhs
, rhs
, target_name
);
249 target
= LLVMBuildSub(fn
->builder
, lhs
, rhs
, target_name
);
252 if (symbol_is_fp_type(insn
->type
))
253 target
= LLVMBuildFMul(fn
->builder
, lhs
, rhs
, target_name
);
255 target
= LLVMBuildMul(fn
->builder
, lhs
, rhs
, target_name
);
258 assert(!symbol_is_fp_type(insn
->type
));
259 target
= LLVMBuildMul(fn
->builder
, lhs
, rhs
, target_name
);
262 if (symbol_is_fp_type(insn
->type
))
263 target
= LLVMBuildFDiv(fn
->builder
, lhs
, rhs
, target_name
);
265 target
= LLVMBuildUDiv(fn
->builder
, lhs
, rhs
, target_name
);
268 assert(!symbol_is_fp_type(insn
->type
));
269 target
= LLVMBuildSDiv(fn
->builder
, lhs
, rhs
, target_name
);
272 assert(!symbol_is_fp_type(insn
->type
));
273 target
= LLVMBuildURem(fn
->builder
, lhs
, rhs
, target_name
);
276 assert(!symbol_is_fp_type(insn
->type
));
277 target
= LLVMBuildSRem(fn
->builder
, lhs
, rhs
, target_name
);
280 assert(!symbol_is_fp_type(insn
->type
));
281 target
= LLVMBuildShl(fn
->builder
, lhs
, rhs
, target_name
);
284 assert(!symbol_is_fp_type(insn
->type
));
285 target
= LLVMBuildLShr(fn
->builder
, lhs
, rhs
, target_name
);
288 assert(!symbol_is_fp_type(insn
->type
));
289 target
= LLVMBuildAShr(fn
->builder
, lhs
, rhs
, target_name
);
294 assert(!symbol_is_fp_type(insn
->type
));
295 target
= LLVMBuildAnd(fn
->builder
, lhs
, rhs
, target_name
);
298 assert(!symbol_is_fp_type(insn
->type
));
299 target
= LLVMBuildOr(fn
->builder
, lhs
, rhs
, target_name
);
302 assert(!symbol_is_fp_type(insn
->type
));
303 target
= LLVMBuildXor(fn
->builder
, lhs
, rhs
, target_name
);
312 /* Binary comparison */
314 assert(!symbol_is_fp_type(insn
->type
));
315 target
= LLVMBuildICmp(fn
->builder
, LLVMIntEQ
, lhs
, rhs
, target_name
);
318 assert(!symbol_is_fp_type(insn
->type
));
319 target
= LLVMBuildICmp(fn
->builder
, LLVMIntNE
, lhs
, rhs
, target_name
);
328 assert(!symbol_is_fp_type(insn
->type
));
329 target
= LLVMBuildICmp(fn
->builder
, LLVMIntSLT
, lhs
, rhs
, target_name
);
332 assert(!symbol_is_fp_type(insn
->type
));
333 target
= LLVMBuildICmp(fn
->builder
, LLVMIntSGT
, lhs
, rhs
, target_name
);
352 insn
->target
->priv
= target
;
355 static void output_op_ret(struct function
*fn
, struct instruction
*insn
)
357 pseudo_t pseudo
= insn
->src
;
359 if (pseudo
&& pseudo
!= VOID
) {
360 LLVMValueRef result
= pseudo_to_value(fn
, pseudo
);
362 LLVMBuildRet(fn
->builder
, result
);
364 LLVMBuildRetVoid(fn
->builder
);
367 static void output_op_load(struct function
*fn
, struct instruction
*insn
)
369 LLVMTypeRef int_type
;
370 LLVMValueRef src_p
, src_i
, ofs_i
, addr_i
, addr
, target
;
372 /* int type large enough to hold a pointer */
373 int_type
= LLVMIntType(bits_in_pointer
);
375 /* convert to integer, add src + offset */
376 src_p
= pseudo_to_value(fn
, insn
->src
);
377 src_i
= LLVMBuildPtrToInt(fn
->builder
, src_p
, int_type
, "src_i");
379 ofs_i
= LLVMConstInt(int_type
, insn
->offset
, 0);
380 addr_i
= LLVMBuildAdd(fn
->builder
, src_i
, ofs_i
, "addr_i");
382 /* convert address back to pointer */
383 addr
= LLVMBuildIntToPtr(fn
->builder
, addr_i
,
384 LLVMPointerType(int_type
, 0), "addr");
387 target
= LLVMBuildLoad(fn
->builder
, addr
, "load_target");
389 insn
->target
->priv
= target
;
392 static void output_op_br(struct function
*fn
, struct instruction
*br
)
395 LLVMValueRef cond
= pseudo_to_value(fn
, br
->cond
);
397 LLVMBuildCondBr(fn
->builder
, cond
,
401 LLVMBuildBr(fn
->builder
,
402 br
->bb_true
? br
->bb_true
->priv
:
406 static void output_op_sel(struct function
*fn
, struct instruction
*insn
)
408 LLVMValueRef target
, src1
, src2
, src3
;
410 src1
= pseudo_to_value(fn
, insn
->src1
);
411 src2
= pseudo_to_value(fn
, insn
->src2
);
412 src3
= pseudo_to_value(fn
, insn
->src3
);
414 target
= LLVMBuildSelect(fn
->builder
, src1
, src2
, src3
, "select");
416 insn
->target
->priv
= target
;
419 static void output_op_switch(struct function
*fn
, struct instruction
*insn
)
421 LLVMValueRef sw_val
, target
;
422 struct basic_block
*def
= NULL
;
423 struct multijmp
*jmp
;
426 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
427 if (jmp
->begin
== jmp
->end
) { /* case N */
429 } else if (jmp
->begin
< jmp
->end
) { /* case M..N */
431 } else /* default case */
433 } END_FOR_EACH_PTR(jmp
);
435 sw_val
= pseudo_to_value(fn
, insn
->target
);
436 target
= LLVMBuildSwitch(fn
->builder
, sw_val
,
437 def
? def
->priv
: NULL
, n_jmp
);
439 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
440 if (jmp
->begin
== jmp
->end
) { /* case N */
442 LLVMConstInt(LLVMInt32Type(), jmp
->begin
, 0),
444 } else if (jmp
->begin
< jmp
->end
) { /* case M..N */
447 } END_FOR_EACH_PTR(jmp
);
449 insn
->target
->priv
= target
;
453 char name
[256]; /* wasteful */
457 DECLARE_ALLOCATOR(llfunc
);
458 DECLARE_PTR_LIST(llfunc_list
, struct llfunc
);
459 ALLOCATOR(llfunc
, "llfuncs");
461 static struct local_module
{
462 struct llfunc_list
*llfunc_list
;
465 static LLVMTypeRef
get_func_type(struct function
*fn
, struct instruction
*insn
)
467 struct symbol
*sym
= insn
->func
->sym
;
469 LLVMTypeRef func_type
, ret_type
;
472 LLVMTypeRef
*arg_type
;
474 sprintf(buffer
, "%.*s", sym
->ident
->len
, sym
->ident
->name
);
476 /* VERIFY: is this correct, for functions? */
477 func_type
= LLVMGetTypeByName(fn
->module
, buffer
);
481 /* to avoid strangeness with varargs [for now], we build
482 * the function and type anew, for each call. This
483 * is probably wrong. We should look up the
484 * symbol declaration info.
487 /* build return type */
488 if (insn
->target
&& insn
->target
!= VOID
)
489 ret_type
= pseudo_type(fn
, insn
->target
);
491 ret_type
= LLVMVoidType();
493 /* count args, build argument type information */
494 FOR_EACH_PTR(insn
->arguments
, arg
) {
496 } END_FOR_EACH_PTR(arg
);
498 arg_type
= calloc(n_arg
, sizeof(LLVMTypeRef
));
501 FOR_EACH_PTR(insn
->arguments
, arg
) {
502 arg_type
[idx
++] = pseudo_type(fn
, arg
);
503 } END_FOR_EACH_PTR(arg
);
505 func_type
= LLVMFunctionType(ret_type
, arg_type
, n_arg
,
511 static LLVMValueRef
get_function(struct function
*fn
, struct instruction
*insn
)
513 struct symbol
*sym
= insn
->func
->sym
;
518 sprintf(buffer
, "%.*s", sym
->ident
->len
, sym
->ident
->name
);
520 /* search for pre-built function type definition */
521 FOR_EACH_PTR(mi
.llfunc_list
, f
) {
522 if (!strcmp(f
->name
, buffer
))
523 return f
->func
; /* found match; return */
524 } END_FOR_EACH_PTR(f
);
526 /* build function type definition */
527 LLVMTypeRef func_type
= get_func_type(fn
, insn
);
529 func
= LLVMAddFunction(fn
->module
, buffer
, func_type
);
531 /* store built function on list, for later */
532 f
= calloc(1, sizeof(*f
));
533 strncpy(f
->name
, buffer
, sizeof(f
->name
) - 1);
536 add_ptr_list(&mi
.llfunc_list
, f
);
541 static void output_op_call(struct function
*fn
, struct instruction
*insn
)
543 LLVMValueRef target
, func
;
548 FOR_EACH_PTR(insn
->arguments
, arg
) {
550 } END_FOR_EACH_PTR(arg
);
552 args
= calloc(n_arg
, sizeof(LLVMValueRef
));
555 FOR_EACH_PTR(insn
->arguments
, arg
) {
556 args
[i
++] = pseudo_to_value(fn
, arg
);
557 } END_FOR_EACH_PTR(arg
);
559 func
= get_function(fn
, insn
);
560 target
= LLVMBuildCall(fn
->builder
, func
, args
, n_arg
, "");
562 insn
->target
->priv
= target
;
565 static void output_op_phi(struct function
*fn
, struct instruction
*insn
)
570 target
= LLVMBuildPhi(fn
->builder
, symbol_type(insn
->type
),
573 FOR_EACH_PTR(insn
->phi_list
, phi
) {
574 if (pseudo_to_value(fn
, phi
)) /* skip VOID */
576 } END_FOR_EACH_PTR(phi
);
578 LLVMValueRef
*phi_vals
= calloc(pll
, sizeof(LLVMValueRef
));
579 LLVMBasicBlockRef
*phi_blks
= calloc(pll
, sizeof(LLVMBasicBlockRef
));
582 FOR_EACH_PTR(insn
->phi_list
, phi
) {
585 v
= pseudo_to_value(fn
, phi
);
586 if (v
) { /* skip VOID */
588 phi_blks
[idx
] = phi
->def
->bb
->priv
;
591 } END_FOR_EACH_PTR(phi
);
593 LLVMAddIncoming(target
, phi_vals
, phi_blks
, pll
);
595 insn
->target
->priv
= target
;
598 static void output_op_cast(struct function
*fn
, struct instruction
*insn
)
600 LLVMValueRef src
, target
;
601 char target_name
[64];
603 src
= insn
->src
->priv
;
605 pseudo_name(insn
->target
, target_name
);
607 if (symbol_is_fp_type(insn
->type
))
608 target
= LLVMBuildFPCast(fn
->builder
, src
, symbol_type(insn
->type
), target_name
);
610 target
= LLVMBuildIntCast(fn
->builder
, src
, symbol_type(insn
->type
), target_name
);
612 insn
->target
->priv
= target
;
615 static void output_insn(struct function
*fn
, struct instruction
*insn
)
617 switch (insn
->opcode
) {
619 output_op_ret(fn
, insn
);
622 output_op_br(fn
, insn
);
631 output_op_switch(fn
, insn
);
633 case OP_COMPUTEDGOTO
:
638 insn
->target
->priv
= pseudo_to_value(fn
, insn
->phi_src
);
641 output_op_phi(fn
, insn
);
644 output_op_load(fn
, insn
);
649 case OP_STORE
: case OP_SNOP
:
652 case OP_INLINED_CALL
:
656 output_op_call(fn
, insn
);
659 output_op_cast(fn
, insn
);
670 case OP_BINARY
... OP_BINARY_END
:
671 case OP_BINCMP
... OP_BINCMP_END
:
672 output_op_binary(fn
, insn
);
675 output_op_sel(fn
, insn
);
681 LLVMValueRef src
, target
;
682 char target_name
[64];
684 src
= pseudo_to_value(fn
, insn
->src
);
686 pseudo_name(insn
->target
, target_name
);
688 target
= LLVMBuildNot(fn
->builder
, src
, target_name
);
690 insn
->target
->priv
= target
;
712 LLVMValueRef src
, target
;
713 char target_name
[64];
715 pseudo_name(insn
->target
, target_name
);
716 src
= pseudo_to_value(fn
, insn
->src
);
718 target
= LLVMBuildAdd(fn
->builder
, src
,
719 LLVMConstInt(LLVMInt32Type(), 0, 0), target_name
);
721 insn
->target
->priv
= target
;
729 static void output_bb(struct function
*fn
, struct basic_block
*bb
, unsigned long generation
)
731 struct instruction
*insn
;
733 bb
->generation
= generation
;
735 FOR_EACH_PTR(bb
->insns
, insn
) {
739 output_insn(fn
, insn
);
741 END_FOR_EACH_PTR(insn
);
746 static void output_fn(LLVMModuleRef module
, struct entrypoint
*ep
)
748 unsigned long generation
= ++bb_generation
;
749 struct symbol
*sym
= ep
->name
;
750 struct symbol
*base_type
= sym
->ctype
.base_type
;
751 struct symbol
*ret_type
= sym
->ctype
.base_type
->ctype
.base_type
;
752 LLVMTypeRef arg_types
[MAX_ARGS
];
753 LLVMTypeRef return_type
;
754 struct function function
;
755 struct basic_block
*bb
;
760 FOR_EACH_PTR(base_type
->arguments
, arg
) {
761 struct symbol
*arg_base_type
= arg
->ctype
.base_type
;
763 arg_types
[nr_args
++] = symbol_type(arg_base_type
);
764 } END_FOR_EACH_PTR(arg
);
766 name
= show_ident(sym
->ident
);
768 return_type
= symbol_type(ret_type
);
770 function
.module
= module
;
772 function
.type
= LLVMFunctionType(return_type
, arg_types
, nr_args
, 0);
774 function
.fn
= LLVMAddFunction(module
, name
, function
.type
);
775 LLVMSetFunctionCallConv(function
.fn
, LLVMCCallConv
);
777 LLVMSetLinkage(function
.fn
, function_linkage(sym
));
779 function
.builder
= LLVMCreateBuilder();
783 FOR_EACH_PTR(ep
->bbs
, bb
) {
784 if (bb
->generation
== generation
)
787 LLVMBasicBlockRef bbr
;
790 sprintf(bbname
, "L%d", nr_bb
++);
791 bbr
= LLVMAppendBasicBlock(function
.fn
, bbname
);
795 END_FOR_EACH_PTR(bb
);
797 FOR_EACH_PTR(ep
->bbs
, bb
) {
798 if (bb
->generation
== generation
)
801 LLVMPositionBuilderAtEnd(function
.builder
, bb
->priv
);
803 output_bb(&function
, bb
, generation
);
805 END_FOR_EACH_PTR(bb
);
808 static int output_data(LLVMModuleRef module
, struct symbol
*sym
)
810 struct expression
*initializer
= sym
->initializer
;
811 unsigned long long initial_value
= 0;
816 if (initializer
->type
== EXPR_VALUE
)
817 initial_value
= initializer
->value
;
822 name
= show_ident(sym
->ident
);
824 data
= LLVMAddGlobal(module
, symbol_type(sym
->ctype
.base_type
), name
);
826 LLVMSetLinkage(data
, data_linkage(sym
));
828 LLVMSetInitializer(data
, LLVMConstInt(symbol_type(sym
), initial_value
, 1));
833 static int compile(LLVMModuleRef module
, struct symbol_list
*list
)
837 FOR_EACH_PTR(list
, sym
) {
838 struct entrypoint
*ep
;
840 ep
= linearize_symbol(sym
);
842 output_fn(module
, ep
);
844 output_data(module
, sym
);
846 END_FOR_EACH_PTR(sym
);
851 int main(int argc
, char **argv
)
853 struct string_list
* filelist
= NULL
;
856 LLVMModuleRef module
= LLVMModuleCreateWithName("sparse");
858 compile(module
, sparse_initialize(argc
, argv
, &filelist
));
860 FOR_EACH_PTR_NOTAG(filelist
, file
) {
861 compile(module
, sparse(file
));
862 } END_FOR_EACH_PTR_NOTAG(file
);
864 LLVMWriteBitcodeToFD(module
, STDOUT_FILENO
, 0, 0);
866 LLVMDisposeModule(module
);