# 1 "stack_gen.c" # 1 "" # 1 "" # 1 "stack_gen.c" # 1 "blocks.h" 1 # 1 "collections.h" 1 # 1 "/usr/include/stdio.h" 1 3 4 # 28 "/usr/include/stdio.h" 3 4 # 1 "/usr/include/features.h" 1 3 4 # 308 "/usr/include/features.h" 3 4 # 1 "/usr/include/sys/cdefs.h" 1 3 4 # 309 "/usr/include/features.h" 2 3 4 # 331 "/usr/include/features.h" 3 4 # 1 "/usr/include/gnu/stubs.h" 1 3 4 # 332 "/usr/include/features.h" 2 3 4 # 29 "/usr/include/stdio.h" 2 3 4 # 1 "/usr/lib/gcc-lib/i486-slackware-linux/3.3.4/include/stddef.h" 1 3 4 # 213 "/usr/lib/gcc-lib/i486-slackware-linux/3.3.4/include/stddef.h" 3 4 typedef unsigned int size_t; # 35 "/usr/include/stdio.h" 2 3 4 # 1 "/usr/include/bits/types.h" 1 3 4 # 28 "/usr/include/bits/types.h" 3 4 # 1 "/usr/include/bits/wordsize.h" 1 3 4 # 29 "/usr/include/bits/types.h" 2 3 4 # 1 "/usr/lib/gcc-lib/i486-slackware-linux/3.3.4/include/stddef.h" 1 3 4 # 32 "/usr/include/bits/types.h" 2 3 4 typedef unsigned char __u_char; typedef unsigned short int __u_short; typedef unsigned int __u_int; typedef unsigned long int __u_long; typedef signed char __int8_t; typedef unsigned char __uint8_t; typedef signed short int __int16_t; typedef unsigned short int __uint16_t; typedef signed int __int32_t; typedef unsigned int __uint32_t; # 62 "/usr/include/bits/types.h" 3 4 typedef struct { long __val[2]; } __quad_t; typedef struct { __u_long __val[2]; } __u_quad_t; # 129 "/usr/include/bits/types.h" 3 4 # 1 "/usr/include/bits/typesizes.h" 1 3 4 # 130 "/usr/include/bits/types.h" 2 3 4 typedef __u_quad_t __dev_t; typedef unsigned int __uid_t; typedef unsigned int __gid_t; typedef unsigned long int __ino_t; typedef __u_quad_t __ino64_t; typedef unsigned int __mode_t; typedef unsigned int __nlink_t; typedef long int __off_t; typedef __quad_t __off64_t; typedef int __pid_t; typedef struct { int __val[2]; } __fsid_t; typedef long int __clock_t; typedef unsigned long int __rlim_t; typedef __u_quad_t __rlim64_t; typedef unsigned int __id_t; typedef long int __time_t; typedef unsigned int __useconds_t; typedef long int __suseconds_t; typedef int __daddr_t; typedef long int __swblk_t; typedef int __key_t; typedef int __clockid_t; typedef int __timer_t; typedef long int __blksize_t; typedef long int __blkcnt_t; typedef __quad_t __blkcnt64_t; typedef unsigned long int __fsblkcnt_t; typedef __u_quad_t __fsblkcnt64_t; typedef unsigned long int __fsfilcnt_t; typedef __u_quad_t __fsfilcnt64_t; typedef int __ssize_t; typedef __off64_t __loff_t; typedef __quad_t *__qaddr_t; typedef char *__caddr_t; typedef int __intptr_t; typedef unsigned int __socklen_t; # 37 "/usr/include/stdio.h" 2 3 4 typedef struct _IO_FILE FILE; # 62 "/usr/include/stdio.h" 3 4 typedef struct _IO_FILE __FILE; # 72 "/usr/include/stdio.h" 3 4 # 1 "/usr/include/libio.h" 1 3 4 # 32 "/usr/include/libio.h" 3 4 # 1 "/usr/include/_G_config.h" 1 3 4 # 14 "/usr/include/_G_config.h" 3 4 # 1 "/usr/lib/gcc-lib/i486-slackware-linux/3.3.4/include/stddef.h" 1 3 4 # 325 "/usr/lib/gcc-lib/i486-slackware-linux/3.3.4/include/stddef.h" 3 4 typedef long int wchar_t; # 354 "/usr/lib/gcc-lib/i486-slackware-linux/3.3.4/include/stddef.h" 3 4 typedef unsigned int wint_t; # 15 "/usr/include/_G_config.h" 2 3 4 # 24 "/usr/include/_G_config.h" 3 4 # 1 "/usr/include/wchar.h" 1 3 4 # 48 "/usr/include/wchar.h" 3 4 # 1 "/usr/lib/gcc-lib/i486-slackware-linux/3.3.4/include/stddef.h" 1 3 4 # 49 "/usr/include/wchar.h" 2 3 4 # 1 "/usr/include/bits/wchar.h" 1 3 4 # 51 "/usr/include/wchar.h" 2 3 4 # 76 "/usr/include/wchar.h" 3 4 typedef struct { int __count; union { wint_t __wch; char __wchb[4]; } __value; } __mbstate_t; # 25 "/usr/include/_G_config.h" 2 3 4 typedef struct { __off_t __pos; __mbstate_t __state; } _G_fpos_t; typedef struct { __off64_t __pos; __mbstate_t __state; } _G_fpos64_t; # 44 "/usr/include/_G_config.h" 3 4 # 1 "/usr/include/gconv.h" 1 3 4 # 28 "/usr/include/gconv.h" 3 4 # 1 "/usr/include/wchar.h" 1 3 4 # 48 "/usr/include/wchar.h" 3 4 # 1 "/usr/lib/gcc-lib/i486-slackware-linux/3.3.4/include/stddef.h" 1 3 4 # 49 "/usr/include/wchar.h" 2 3 4 # 29 "/usr/include/gconv.h" 2 3 4 # 1 "/usr/lib/gcc-lib/i486-slackware-linux/3.3.4/include/stddef.h" 1 3 4 # 32 "/usr/include/gconv.h" 2 3 4 enum { __GCONV_OK = 0, __GCONV_NOCONV, __GCONV_NODB, __GCONV_NOMEM, __GCONV_EMPTY_INPUT, __GCONV_FULL_OUTPUT, __GCONV_ILLEGAL_INPUT, __GCONV_INCOMPLETE_INPUT, __GCONV_ILLEGAL_DESCRIPTOR, __GCONV_INTERNAL_ERROR }; enum { __GCONV_IS_LAST = 0x0001, __GCONV_IGNORE_ERRORS = 0x0002 }; struct __gconv_step; struct __gconv_step_data; struct __gconv_loaded_object; struct __gconv_trans_data; typedef int (*__gconv_fct) (struct __gconv_step *, struct __gconv_step_data *, const unsigned char **, const unsigned char *, unsigned char **, size_t *, int, int); typedef wint_t (*__gconv_btowc_fct) (struct __gconv_step *, unsigned char); typedef int (*__gconv_init_fct) (struct __gconv_step *); typedef void (*__gconv_end_fct) (struct __gconv_step *); typedef int (*__gconv_trans_fct) (struct __gconv_step *, struct __gconv_step_data *, void *, const unsigned char *, const unsigned char **, const unsigned char *, unsigned char **, size_t *); typedef int (*__gconv_trans_context_fct) (void *, const unsigned char *, const unsigned char *, unsigned char *, unsigned char *); typedef int (*__gconv_trans_query_fct) (const char *, const char ***, size_t *); typedef int (*__gconv_trans_init_fct) (void **, const char *); typedef void (*__gconv_trans_end_fct) (void *); struct __gconv_trans_data { __gconv_trans_fct __trans_fct; __gconv_trans_context_fct __trans_context_fct; __gconv_trans_end_fct __trans_end_fct; void *__data; struct __gconv_trans_data *__next; }; struct __gconv_step { struct __gconv_loaded_object *__shlib_handle; const char *__modname; int __counter; char *__from_name; char *__to_name; __gconv_fct __fct; __gconv_btowc_fct __btowc_fct; __gconv_init_fct __init_fct; __gconv_end_fct __end_fct; int __min_needed_from; int __max_needed_from; int __min_needed_to; int __max_needed_to; int __stateful; void *__data; }; struct __gconv_step_data { unsigned char *__outbuf; unsigned char *__outbufend; int __flags; int __invocation_counter; int __internal_use; __mbstate_t *__statep; __mbstate_t __state; struct __gconv_trans_data *__trans; }; typedef struct __gconv_info { size_t __nsteps; struct __gconv_step *__steps; struct __gconv_step_data __data [1]; } *__gconv_t; # 45 "/usr/include/_G_config.h" 2 3 4 typedef union { struct __gconv_info __cd; struct { struct __gconv_info __cd; struct __gconv_step_data __data; } __combined; } _G_iconv_t; typedef int _G_int16_t ; typedef int _G_int32_t ; typedef unsigned int _G_uint16_t ; typedef unsigned int _G_uint32_t ; # 33 "/usr/include/libio.h" 2 3 4 # 53 "/usr/include/libio.h" 3 4 # 1 "/usr/lib/gcc-lib/i486-slackware-linux/3.3.4/include/stdarg.h" 1 3 4 # 43 "/usr/lib/gcc-lib/i486-slackware-linux/3.3.4/include/stdarg.h" 3 4 typedef __builtin_va_list __gnuc_va_list; # 54 "/usr/include/libio.h" 2 3 4 # 166 "/usr/include/libio.h" 3 4 struct _IO_jump_t; struct _IO_FILE; # 176 "/usr/include/libio.h" 3 4 typedef void _IO_lock_t; struct _IO_marker { struct _IO_marker *_next; struct _IO_FILE *_sbuf; int _pos; # 199 "/usr/include/libio.h" 3 4 }; enum __codecvt_result { __codecvt_ok, __codecvt_partial, __codecvt_error, __codecvt_noconv }; # 267 "/usr/include/libio.h" 3 4 struct _IO_FILE { int _flags; char* _IO_read_ptr; char* _IO_read_end; char* _IO_read_base; char* _IO_write_base; char* _IO_write_ptr; char* _IO_write_end; char* _IO_buf_base; char* _IO_buf_end; char *_IO_save_base; char *_IO_backup_base; char *_IO_save_end; struct _IO_marker *_markers; struct _IO_FILE *_chain; int _fileno; int _flags2; __off_t _old_offset; unsigned short _cur_column; signed char _vtable_offset; char _shortbuf[1]; _IO_lock_t *_lock; # 315 "/usr/include/libio.h" 3 4 __off64_t _offset; void *__pad1; void *__pad2; int _mode; char _unused2[15 * sizeof (int) - 2 * sizeof (void *)]; }; typedef struct _IO_FILE _IO_FILE; struct _IO_FILE_plus; extern struct _IO_FILE_plus _IO_2_1_stdin_; extern struct _IO_FILE_plus _IO_2_1_stdout_; extern struct _IO_FILE_plus _IO_2_1_stderr_; # 354 "/usr/include/libio.h" 3 4 typedef __ssize_t __io_read_fn (void *__cookie, char *__buf, size_t __nbytes); typedef __ssize_t __io_write_fn (void *__cookie, const char *__buf, size_t __n); typedef int __io_seek_fn (void *__cookie, __off64_t *__pos, int __w); typedef int __io_close_fn (void *__cookie); # 406 "/usr/include/libio.h" 3 4 extern int __underflow (_IO_FILE *) ; extern int __uflow (_IO_FILE *) ; extern int __overflow (_IO_FILE *, int) ; extern wint_t __wunderflow (_IO_FILE *) ; extern wint_t __wuflow (_IO_FILE *) ; extern wint_t __woverflow (_IO_FILE *, wint_t) ; # 444 "/usr/include/libio.h" 3 4 extern int _IO_getc (_IO_FILE *__fp) ; extern int _IO_putc (int __c, _IO_FILE *__fp) ; extern int _IO_feof (_IO_FILE *__fp) ; extern int _IO_ferror (_IO_FILE *__fp) ; extern int _IO_peekc_locked (_IO_FILE *__fp) ; extern void _IO_flockfile (_IO_FILE *) ; extern void _IO_funlockfile (_IO_FILE *) ; extern int _IO_ftrylockfile (_IO_FILE *) ; # 474 "/usr/include/libio.h" 3 4 extern int _IO_vfscanf (_IO_FILE * , const char * , __gnuc_va_list, int *) ; extern int _IO_vfprintf (_IO_FILE *, const char *, __gnuc_va_list) ; extern __ssize_t _IO_padn (_IO_FILE *, int, __ssize_t) ; extern size_t _IO_sgetn (_IO_FILE *, void *, size_t) ; extern __off64_t _IO_seekoff (_IO_FILE *, __off64_t, int, int) ; extern __off64_t _IO_seekpos (_IO_FILE *, __off64_t, int) ; extern void _IO_free_backup_area (_IO_FILE *) ; # 73 "/usr/include/stdio.h" 2 3 4 # 86 "/usr/include/stdio.h" 3 4 typedef _G_fpos_t fpos_t; # 138 "/usr/include/stdio.h" 3 4 # 1 "/usr/include/bits/stdio_lim.h" 1 3 4 # 139 "/usr/include/stdio.h" 2 3 4 extern struct _IO_FILE *stdin; extern struct _IO_FILE *stdout; extern struct _IO_FILE *stderr; extern int remove (const char *__filename) ; extern int rename (const char *__old, const char *__new) ; extern FILE *tmpfile (void); # 178 "/usr/include/stdio.h" 3 4 extern char *tmpnam (char *__s) ; extern char *tmpnam_r (char *__s) ; # 196 "/usr/include/stdio.h" 3 4 extern char *tempnam (const char *__dir, const char *__pfx) ; extern int fclose (FILE *__stream); extern int fflush (FILE *__stream); # 221 "/usr/include/stdio.h" 3 4 extern int fflush_unlocked (FILE *__stream); # 235 "/usr/include/stdio.h" 3 4 extern FILE *fopen (const char * __filename, const char * __modes); extern FILE *freopen (const char * __filename, const char * __modes, FILE * __stream); # 262 "/usr/include/stdio.h" 3 4 # 273 "/usr/include/stdio.h" 3 4 extern FILE *fdopen (int __fd, const char *__modes) ; # 294 "/usr/include/stdio.h" 3 4 extern void setbuf (FILE * __stream, char * __buf) ; extern int setvbuf (FILE * __stream, char * __buf, int __modes, size_t __n) ; extern void setbuffer (FILE * __stream, char * __buf, size_t __size) ; extern void setlinebuf (FILE *__stream) ; extern int fprintf (FILE * __stream, const char * __format, ...); extern int printf (const char * __format, ...); extern int sprintf (char * __s, const char * __format, ...) ; extern int vfprintf (FILE * __s, const char * __format, __gnuc_va_list __arg); extern int vprintf (const char * __format, __gnuc_va_list __arg); extern int vsprintf (char * __s, const char * __format, __gnuc_va_list __arg) ; extern int snprintf (char * __s, size_t __maxlen, const char * __format, ...) ; extern int vsnprintf (char * __s, size_t __maxlen, const char * __format, __gnuc_va_list __arg) ; # 388 "/usr/include/stdio.h" 3 4 extern int fscanf (FILE * __stream, const char * __format, ...); extern int scanf (const char * __format, ...); extern int sscanf (const char * __s, const char * __format, ...) ; # 430 "/usr/include/stdio.h" 3 4 extern int fgetc (FILE *__stream); extern int getc (FILE *__stream); extern int getchar (void); # 454 "/usr/include/stdio.h" 3 4 extern int getc_unlocked (FILE *__stream); extern int getchar_unlocked (void); # 465 "/usr/include/stdio.h" 3 4 extern int fgetc_unlocked (FILE *__stream); extern int fputc (int __c, FILE *__stream); extern int putc (int __c, FILE *__stream); extern int putchar (int __c); # 498 "/usr/include/stdio.h" 3 4 extern int fputc_unlocked (int __c, FILE *__stream); extern int putc_unlocked (int __c, FILE *__stream); extern int putchar_unlocked (int __c); extern int getw (FILE *__stream); extern int putw (int __w, FILE *__stream); extern char *fgets (char * __s, int __n, FILE * __stream); extern char *gets (char *__s); # 578 "/usr/include/stdio.h" 3 4 extern int fputs (const char * __s, FILE * __stream); extern int puts (const char *__s); extern int ungetc (int __c, FILE *__stream); extern size_t fread (void * __ptr, size_t __size, size_t __n, FILE * __stream); extern size_t fwrite (const void * __ptr, size_t __size, size_t __n, FILE * __s); # 631 "/usr/include/stdio.h" 3 4 extern size_t fread_unlocked (void * __ptr, size_t __size, size_t __n, FILE * __stream); extern size_t fwrite_unlocked (const void * __ptr, size_t __size, size_t __n, FILE * __stream); extern int fseek (FILE *__stream, long int __off, int __whence); extern long int ftell (FILE *__stream); extern void rewind (FILE *__stream); # 686 "/usr/include/stdio.h" 3 4 extern int fgetpos (FILE * __stream, fpos_t * __pos); extern int fsetpos (FILE *__stream, const fpos_t *__pos); # 709 "/usr/include/stdio.h" 3 4 # 718 "/usr/include/stdio.h" 3 4 extern void clearerr (FILE *__stream) ; extern int feof (FILE *__stream) ; extern int ferror (FILE *__stream) ; extern void clearerr_unlocked (FILE *__stream) ; extern int feof_unlocked (FILE *__stream) ; extern int ferror_unlocked (FILE *__stream) ; extern void perror (const char *__s); # 1 "/usr/include/bits/sys_errlist.h" 1 3 4 # 27 "/usr/include/bits/sys_errlist.h" 3 4 extern int sys_nerr; extern const char *const sys_errlist[]; # 748 "/usr/include/stdio.h" 2 3 4 extern int fileno (FILE *__stream) ; extern int fileno_unlocked (FILE *__stream) ; # 767 "/usr/include/stdio.h" 3 4 extern FILE *popen (const char *__command, const char *__modes); extern int pclose (FILE *__stream); extern char *ctermid (char *__s) ; # 807 "/usr/include/stdio.h" 3 4 extern void flockfile (FILE *__stream) ; extern int ftrylockfile (FILE *__stream) ; extern void funlockfile (FILE *__stream) ; # 834 "/usr/include/stdio.h" 3 4 # 4 "collections.h" 2 typedef struct bit_set* BitSet; BitSet set_new(int size); BitSet set_clone(BitSet original); void set_add(BitSet set, int n); void moveBit(BitSet set, int to, int from); void set_fix(BitSet set); int set_equals(BitSet set1, BitSet set2); void set_remove(BitSet set, int n); int set_contains_function(BitSet set, int n); void set_print(FILE* file, BitSet set); void set_clear(BitSet set); int set_next(BitSet set, int from); void set_addSet(BitSet set, const BitSet pattern); void set_removeSet(BitSet set, const BitSet pattern); int set_empty(BitSet set); int set_size(BitSet set); BitSet set_intersection(BitSet set1, BitSet set2); BitSet set_union(BitSet set1, BitSet set2); typedef struct arrayList* ArrayList; ArrayList list_new(int capacity); void list_add(ArrayList list, void* item); void list_remove(ArrayList list, int item); int list_size(ArrayList list); void* list_get(ArrayList list, int n); void list_set(ArrayList list, int n, void* item); void list_sort(ArrayList list, int (*compare)(const void*, const void*)); void list_print(ArrayList list, FILE* out, void (*print)(FILE*, void*)); # 7 "blocks.h" 2 # 1 "x_stack.h" 1 typedef struct x_stack* XStack; XStack xstack_new(BitSet set); # 19 "x_stack.h" void xstack_print(XStack stack, FILE* out); int xstack_contains(XStack x, Symbol s); int xstack_size(XStack x); Symbol xstack_item(XStack x, int i); void xstack_remove(XStack x, int i); ArrayList xstack_top(XStack x, int count); void xstack_ensureReachable(XStack x, BitSet variables, int delve); # 8 "blocks.h" 2 typedef struct block* Block; void initUse(Block b); Node block_firstNode(Block b); Node block_lastNode(Block b); int block_id(Block b); void setBlockID(Block b, int id); void block_setStartEDepth(Block b, int depth); int block_getStartEDepth(Block b); void block_setStartLDepth(Block b, int depth); int block_getStartLDepth(Block b); void block_setEndEDepth(Block b, int depth); int block_getEndEDepth(Block b); void block_setEndLDepth(Block b, int depth); int block_getEndLDepth(Block b); Block block_new(int startDepth, int endDepth, Node first, Node last); void deleteVirtual(Block b, Node temp); BitSet block_def(Block b); BitSet block_use(Block b); BitSet block_livein(Block b); BitSet block_liveout(Block b); Block block_merge(Block b1, Block b2); int block_length(Block b); void block_print(Block b, FILE* out); Node block_firstTemp(Block b); Node block_lastTemp(Block b); BitSet block_accept(Block b); BitSet block_reject(Block b); XStack block_inStack(Block b); XStack block_outStack(Block b); void insertAtHead(Block b, Node forest); void insertAtTail(Block b, Node forest); void block_setInStack(Block b, XStack in); void block_setOutStack(Block b, XStack out); # 2 "stack_gen.c" 2 # 1 "flow.h" 1 # 1 "graph.h" 1 typedef struct graph* Graph; int graph_size(Graph graph); BitSet graph_newNodeSet(Graph graph, int arena); Graph graph_new(void); BitSet graph_children(Graph graph, int parent); BitSet graph_parents(Graph graph, int child); int graph_addNode(Graph graph, void* data); void graph_addEdge(Graph graph, int from, int to); void graph_close(Graph graph, void* (* merge)(void* node1, void* node2)); void* graph_node(Graph graph, int index); void integrity(Graph graph); # 7 "flow.h" 2 typedef struct edge* Edge; typedef struct edgeSet* EdgeSet; extern Graph flow_graph; void flow_applyToBlocks(void (* func)(Block nodeData)); void flow_print(char* out); void flow_printNode(int i, FILE* out); void edgeset_print(EdgeSet set, FILE* out); int flow_addBlock(Block data); void flow_addEdge(int from, int to); void flow_draw(FILE* stream); Block flow_block(int b); void flow_close(void); ArrayList getEdgeSets(void); BitSet edgeset_parents(EdgeSet edges); BitSet edgeset_children(EdgeSet edges); int edgeset_depth(EdgeSet edges); void addEdge(int from, int to); # 3 "stack_gen.c" 2 # 1 "optimise.h" 1 typedef struct _optimiser { char* name; char* description; int level; char* (*function)(void); } optimiser; typedef optimiser* Optimiser; extern int optimiser_count; extern char optimisersOn[]; extern Optimiser optimisers[]; # 4 "stack_gen.c" 2 static void permuteTree(Node tree); static void annotateTree(Node node, int height); extern optimiser cleanup; extern void liveness(); void processForest(Node forest); static void printnode(Node p, FILE* out); static void printsubtree(Node p, char* indent, FILE* out); FILE* logfile = 0; extern int do_verify; static int dump_graph = 0; int framesize; int offset; void write_log(char* format, ...) { if (logfile) { va_list ap; va_start(ap, format); vfprintf(logfile, format, ap); va_end(ap); } } static ArrayList local_variable_list = ((void *)0); void makeTemporary(Symbol p) { p->x.name = p->name; p->sclass = REGISTER; p->x.uniqueID = local_variable_count; if (local_variable_list == ((void *)0)) { local_variable_list = list_new(16); } list_add(local_variable_list, p); local_variable_count++; } void mkauto(Symbol p) { assert(p->sclass == AUTO); offset = roundup(offset + p->type->size, p->type->align); p->x.offset = -offset; p->x.name = stringd(-offset); } int range(Node p, int lo, int hi) { Symbol s = p->syms[0]; Symbol s1; switch (specific(p->op)) { case ADDRL+P: return (s->x.offset >= lo && s->x.offset <= hi) ? 0 : LBURG_MAX; case CNST+I: case TUCK+I: case TUCK+U: case TUCK+F: case TUCK+P: return (s->u.c.v.i >= lo && s->u.c.v.i <= hi) ? 0 : LBURG_MAX; case CNST+U: return (s->u.c.v.u >= lo && s->u.c.v.u <= hi) ? 0 : LBURG_MAX; case CNST+P: return (s->u.c.v.p == 0 && lo <= 0 && hi >= 0) ? 0 : LBURG_MAX; case STACK+P: case COPY+P: s1 = p->syms[1]; return (s1->u.c.v.i >= lo && s1->u.c.v.i <= hi) ? 0 : LBURG_MAX; } return LBURG_MAX; } static Node duplicate(Node n) { if (n) { Node new = newnode(n->op, duplicate(n->kids[0]), duplicate(n->kids[1]), n->syms[0]); new->syms[1] = n->syms[1]; return new; } else { return ((void *)0); } } static void split_if_complex(Node* kid, Node prev) { int op = generic((*kid)->op); Symbol temp; Node tempNode, asgn ; temp = newtemp(AUTO, optype((*kid)->op), opsize((*kid)->op)); tempNode = newnode(VREG + P, ((void *)0), ((void *)0), temp); if (op == INDIR && (*kid)->kids[0]->op == VREG + P) { if ((*kid)->kids[0]->syms[0]->temporary) { return; } } else { if (IR->x.recalcNode(tempNode, *kid) == *kid) return; } if (IR->x.makeVirtual(temp)) { Node indir = newnode(INDIR + (*kid)->op - op, tempNode, ((void *)0), ((void *)0)); temp->x.branchTemp = 1; asgn = newnode(ASGN + (*kid)->op - op, ((void *)0), ((void *)0), intconst( temp->type->size)); asgn->kids[1] = newnode(VREG + P, ((void *)0), ((void *)0), temp); asgn->kids[0] = *kid; asgn->syms[1] = intconst(temp->type->align); *kid = indir; asgn->link = prev->link; prev->link = asgn; } } static void flattenTest(Node test, Node prev) { split_if_complex(&(test->kids[1]), prev); split_if_complex(&(test->kids[0]), prev); } static void flattenForest(Node forest) { Node prev = ((void *)0); Node p, test; for (p = forest; p; p = p->link) { switch(generic(p->op)) { case EQ: case GE: case LT: case GT: case NE: case LE: if (prev == ((void *)0)) { test = duplicate(p); test->syms[1] = p->syms[1]; test->link = p->link; p->link = test; p->op = NOOP; p->kids[0] = ((void *)0); p->kids[1] = ((void *)0); p->syms[0] = ((void *)0); p->syms[1] = ((void *)0); flattenTest(test, p); p = test; } else { flattenTest(p, prev); } case RET: case JUMP: prev = ((void *)0); default: prev = p; } } } static Node eliminateCSE(Node p) { if (p == ((void *)0)) return ((void *)0); if (generic(p->op) == INDIR && p->kids[0]->op == VREG+P) { Symbol r = p->kids[0]->syms[0]; if (r->u.t.cse) { Node n = (IR->x.recalcNode)(p, r->u.t.cse); assert(n == p || n == r->u.t.cse); return n == p ? n : duplicate(n); } } p->kids[0] = eliminateCSE(p->kids[0]); p->kids[1] = eliminateCSE(p->kids[1]); return p; } static void prepare(Node p) { Symbol s; if (p == ((void *)0)) return; prepare(p->kids[0]); prepare(p->kids[1]); s = p->syms[0]; switch (generic(p->op)) { case ADDRF: if (s->scope == PARAM) break; p->op += ADDRL - ADDRF; case ADDRL: if (s->sclass == REGISTER) p->op = VREG+P; break; } } static void swapkids(Node node) { Node swap = node->kids[0]; assert(node->kids[0]); assert(node->kids[1]); node->kids[0] = node->kids[1]; node->kids[1] = swap; } static void permuteTree(Node tree) { if (tree == ((void *)0)) return; switch (generic(tree->op)) { case ASGN: swapkids(tree); break; case SUB: if (IR->x.rhs.sub) { swapkids(tree); } break; case LSH: if (IR->x.rhs.lsh) { swapkids(tree); } break; case RSH: if (IR->x.rhs.rsh) { swapkids(tree); } break; case MOD: if (IR->x.rhs.mod) { swapkids(tree); } break; case DIV: if (IR->x.rhs.div) { swapkids(tree); } break; case LT: if (IR->x.rhs.lt) { swapkids(tree); } break; case LE: if (IR->x.rhs.le) { swapkids(tree); } break; case GT: if (IR->x.rhs.gt) { swapkids(tree); } break; case GE: if (IR->x.rhs.ge) { swapkids(tree); } break; case ADD: case MUL: case EQ: case NE: case BAND: case BXOR: case BOR: if (specific(tree->kids[0]->op) == CNST + I) { swapkids(tree); } } permuteTree(tree->kids[0]); permuteTree(tree->kids[1]); } static Node lastTemp; static void annotate(Node forest) { Node p; int height = 0; lastTemp = ((void *)0); for (p = forest; p; p = p->link) { switch (generic(p->op)) { case EQ: case GE: case LT: case GT: case NE: case LE: annotateTree(p, height); break; case JUMP: annotateTree(p, height); break; case ARG: annotateTree(p, height); height += (opsize(p->op) == 8 ? 2 : 1); break; case LABEL: case NOOP: break; case CALL: annotateTree(p, height); height = 0; break; case RET: assert(height == 0); annotateTree(p, height); break; case ASGN: if(generic(p->kids[0]->op) == CALL) { annotateTree(p->kids[0], height); height = (opsize(p->kids[0]->op) == 8 ? 2 : 1); annotateTree(p->kids[1], height); height = 0; } else if(generic(p->kids[1]->op) == CALL) { annotateTree(p->kids[1], height); height = (opsize(p->kids[1]->op) == 8 ? 2 : 1); annotateTree(p->kids[0], height); height = 0; } else if (generic(p->kids[0]->op) == VREG) { annotateTree(p->kids[1], height); annotateTree(p->kids[0], height + (opsize(p->kids[0]->op) == 8 ? 2 : 1)); } else { annotateTree(p->kids[0], height); annotateTree(p->kids[1], height + (opsize(p->kids[0]->op) == 8 ? 2 : 1)); } break; default: assert(0); } } } int getEDepth(Node n) { assert(generic(n->op) == VREG || generic(n->op) == COPY || generic(n->op) == STACK); return n->x.e_depth; } int getTotalDepth(Node n) { assert(generic(n->op) == VREG || generic(n->op) == COPY || generic(n->op) == STACK); return n->x.l_depth + n->x.e_depth; } int getDelve(Node n) { return n->syms[1]->u.c.v.i; } static Symbol ICONSTS[] = { ((void *)0), ((void *)0), ((void *)0), ((void *)0), ((void *)0) }; void setDelve(Node n, int delve) { assert(delve > 0); if (delve < 5) { if (ICONSTS[delve] == ((void *)0)) ICONSTS[delve] = intconst(delve); n->syms[1] = ICONSTS[delve]; } else { n->syms[1] = intconst(delve); } } static void annotateTree(Node node, int height) { int generic = generic(node->op); if (generic == VREG) { node->x.e_depth = height; } else if (node->kids[0]) { annotateTree(node->kids[0], height); if (node->kids[1]) { annotateTree(node->kids[1], height + (opsize(node->kids[0]->op) == 8 ? 2 : 1)); } } } static int fallThrough = -1; static int table_jump = -1; int local_variable_count; Symbol localVariableSymbol(int n) { return list_get(local_variable_list, n); } void insertBranchEdges(); extern optimiser dumpflow; void optimise() { int i; char* msg; insertBranchEdges(); flow_close(); liveness(); integrity(flow_graph); verify("init"); if (dump_graph) flow_print(stringf("%s%s.init", "/tmp", cfunc->name)); for(i = 0; i < optimiser_count; i++) { if (optimisersOn[i] > 0) { write_log("Calling %s\n", optimisers[i]->name); msg = optimisers[i]->function(); verify(optimisers[i]->name); if (dump_graph) flow_print(stringf("%s%s.%s", "/tmp", cfunc->name, optimisers[i]->name)); if (msg) { fatal(optimisers[i]->name, msg, 0); } } } fallThrough = -1; local_variable_list = ((void *)0); } static void setOptimiser(char* name, int on) { int j; write_log("Optimiser %s on.\n", name); for(j = 0; j < optimiser_count; j++) { if (strcmp(name, optimisers[j]->name) == 0) { optimisersOn[j] = on; return; } } fprintf(stderr, "Cannot find optimiser %s\n", name); exit(1); } void backendflags(int argc, char *argv[]) { int i, j, level = 2; for(j = 0; j < optimiser_count;j++) { optimisersOn[j] = 0; } for (i = 1; i < argc; i++) { char* arg = argv[i]; if (strncmp(arg, "-log", 4) == 0) { if (arg[4] == '\0') { logfile = fopen("lcc.log", "w"); } else { logfile = fopen(arg + 4, "w"); } } else if (strncmp(arg, "-graph", 6) == 0) { dump_graph = 1; } else if (strncmp(arg, "-verify", 7) == 0) { do_verify = 1; } else if (strncmp(arg, "-O", 2) == 0) { if(arg[3]) { setOptimiser(arg + 2, 1); } else { level = arg[2] - '0'; if (level < 0 || level > 3) { fprintf(stderr, "Illegal optimisation level: %s\n", arg + 2); exit(1); } } } } for(j = 0; j < optimiser_count;j++) { if ((optimisers[j]->level & (1 << level)) && (optimisersOn[j] == 0)) { optimisersOn[j] = 1; write_log("Optimiser %s on.\n", optimisers[j]->name); } } } void encode() { } Node popParam(Node destination, int sizeAndType, Node link, int depth) { Node n, tos = newnode(STACK + P, ((void *)0), ((void *)0), destination->syms[0]); setDelve(tos, 1); tos->x.l_depth = depth; tos = newnode(INDIR + sizeAndType, tos, ((void *)0), ((void *)0)); n = newnode(ASGN + sizeAndType, tos, destination, ((void *)0)); n->link = link; assert(n->count == 0); return n; } Node stackParameters(Symbol caller[], Symbol callee[]) { Node last; Block b; Node intro = ((void *)0); int i, sizeAndType, depth = 0; for (i = 0; callee[i]; i++) { Node leftNode; Symbol p = callee[i]; Symbol q = caller[i]; p->scope = LOCAL; assert(q); sizeAndType = ttob(p->type); depth += roundup(p->type->size, IR->ptrmetric.size) / IR->ptrmetric.size; if (IR->x.makeVirtual(p)) { leftNode = newnode(VREG + P, ((void *)0), ((void *)0), p); leftNode->x.l_depth = depth-1; leftNode->x.e_depth = 1; q->sclass = REGISTER; q->type = p->type; } else { mkauto(p); leftNode = newnode(ADDRL + P + sizeop(IR->ptrmetric.size), ((void *)0), ((void *)0), p); } intro = popParam(leftNode, sizeAndType, intro, depth); } assert(!caller[i]); flow_graph = graph_new(); if (!intro) { intro = newnode(NOOP, ((void *)0), ((void *)0), ((void *)0)); } for (last = intro; last->link; last = last->link); b = block_new(0, 0, intro, last); block_setStartLDepth(b, depth); fallThrough = flow_addBlock(b); return intro; } Node stackgen(Node forest) { Node p; assert(forest); for (p = forest; p; p = p->link) { p->x.listed = 1; prepare(p); eliminateCSE(p); permuteTree(p); assert(p->x.registered == 0); } flattenForest(forest); annotate(forest); processForest(forest); return forest; } static ArrayList branches = ((void *)0); typedef struct _branch { int from; Symbol to; } *Branch; void insertBranchEdges() { Branch b; if(branches) { int i = list_size(branches); while(i) { i--; b = (Branch)list_get(branches, i); addEdge(b->from, b->to->sclass); } branches = ((void *)0); } } void newBranch(int block, Symbol to) { Branch item; if (branches == ((void *)0)) { branches = list_new(100); } item = allocate(sizeof(struct _branch), FUNC); item->from = block; item->to = to; list_add(branches, item); } void processForest(Node forest) { int depth = 0; int startDepth = 0; Node first, previous, tree; Symbol label = ((void *)0); int block; first = previous = ((void *)0); tree = forest; while (tree) { switch(generic(tree->op)) { case LABEL: if (first) { block = flow_addBlock(block_new(startDepth, depth, first, previous)); if (fallThrough >= 0) { addEdge(fallThrough, block); } if (label) { label->sclass = block; } fallThrough = block; } label = tree->syms[0]; first = tree; startDepth = depth; break; case LT: case GT: case LE: case GE: case EQ: case NE: case JUMP: if (first) { block = flow_addBlock(block_new(startDepth, depth, first, tree)); } else { block = flow_addBlock(block_new(depth, depth, tree, tree)); } if (label) { label->sclass = block; label = ((void *)0); } if (fallThrough >= 0) { addEdge(fallThrough, block); } if (generic(tree->op) == JUMP) { if (generic(tree->kids[0]->op) == ADDRG) { newBranch(block, tree->kids[0]->syms[0]); } else { table_jump = block; } fallThrough = -1; } else { fallThrough = block; newBranch(block, tree->syms[0]); } first = ((void *)0); startDepth = depth; break; case CALL: depth = 0; goto end; case ARG: depth += (roundup(opsize(tree->op), IR->ptrmetric.size) / IR->ptrmetric.size); goto end; case ASGN: if (generic(tree->kids[0]->op) == CALL) depth = 0; goto end; default: end: if (first == ((void *)0)) first = tree; } previous = tree; tree = tree->link; } if (first) { block = flow_addBlock(block_new(startDepth, depth, first, previous)); if (label) { label->sclass = block; label = ((void *)0); } if (fallThrough >= 0) { addEdge(fallThrough, block); } fallThrough = block; } } void swtch(Symbol s) { newBranch(table_jump, s); } void printTree(Node p, FILE* out) { printsubtree(p, "", out); } void prettytree(Node p) { printsubtree(p, "", stderr); } static void printsubtree(Node p, char* indent, FILE* out) { if (p->kids[1]) { printnode(p, out); fprint(out, indent); fprint(out, "| '-"); printsubtree(p->kids[0], stringf("%s| ", indent), out); fprint(out, indent); fprint(out, "'---"); printsubtree(p->kids[1], stringf("%s ", indent), out); } else if (p->kids[0]) { printnode(p, out); fprintf(out, indent); fprint(out, " '-"); printsubtree(p->kids[0], stringf("%s ", indent), out); } else { printnode(p, out); } } static void printnode(Node p, FILE* out) { fprint(out, "%s ", opname(p->op)); switch (generic(p->op)) { case VREG: fprint(out, "%s ", p->syms[0]->name); fprint(out, "e=%d l=%d", getEDepth(p), p->x.l_depth); fprint(out, " ref: %g", p->syms[0]->ref); break; case STACK: case COPY: if (p->syms[1]) fprint(out, " %d e=%d l=%d", getDelve(p), getEDepth(p), p->x.l_depth); else fprint(out, " NO DELVE e=%d l=%d", getEDepth(p), p->x.l_depth); if (p->syms[0]) fprint(out, " %s", p->syms[0]->name); break; case TUCK: fprint(out, " %d", p->syms[0]->u.c.v.i); break; case CNST: case ADDRG: case ADDRF: case ADDRL: if (p->syms[0]) fprint(out, "%s", p->syms[0]->name); break; case LABEL: fprint(out, "%s", p->syms[0]->name); fprint(out, " ref: %g", p->syms[0]->ref); break; case RET: case NOOP: case CVF: case CVI: case CVP: case CVU: case JUMP: case ARG: case BCOM: case NEG: case INDIR: case CALL: case ASGN: case BOR: case BAND: case BXOR: case RSH: case LSH: case ADD: case SUB: case DIV: case MUL: case MOD: break; case EQ: case NE: case GT: case GE: case LE: case LT: fprint(out, " l%s", p->syms[0]->name); break; default: assert(0); } fprint(out, "\n"); }