2 * 'sparse' library helper routines.
4 * Copyright (C) 2003 Transmeta Corp.
7 * Licensed under the Open Software License version 1.1
18 #include <sys/types.h>
25 #include "expression.h"
27 #include "linearize.h"
30 struct token
*skip_to(struct token
*token
, int op
)
32 while (!match_op(token
, op
) && !eof_token(token
))
37 struct token
*expect(struct token
*token
, int op
, const char *where
)
39 if (!match_op(token
, op
)) {
40 static struct token bad_token
;
41 if (token
!= &bad_token
) {
42 bad_token
.next
= token
;
43 warn(token
->pos
, "Expected %s %s", show_special(op
), where
);
44 warn(token
->pos
, "got %s", show_token(token
));
47 return skip_to(token
, op
);
53 unsigned int hexval(unsigned int c
)
61 retval
= c
- 'a' + 10;
64 retval
= c
- 'A' + 10;
71 * Simple allocator for data that doesn't get partially free'd.
72 * The tokenizer and parser allocate a _lot_ of small data structures
73 * (often just two-three bytes for things like small integers),
74 * and since they all depend on each other you can't free them
75 * individually _anyway_. So do something that is very space-
76 * efficient: allocate larger "blobs", and give out individual
77 * small bits and pieces of it with no maintenance overhead.
79 struct allocation_blob
{
80 struct allocation_blob
*next
;
81 unsigned int left
, offset
;
86 #define blob_alloc(size) mmap(NULL, ((size)+4095) & ~4095, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)
87 #define blob_free(addr,size) munmap((addr), ((size)+4095) & ~4095)
89 struct allocator_struct
{
91 struct allocation_blob
*blobs
;
92 unsigned int alignment
;
93 unsigned int chunking
;
95 unsigned int allocations
, total_bytes
, useful_bytes
;
98 void drop_all_allocations(struct allocator_struct
*desc
)
100 struct allocation_blob
*blob
= desc
->blobs
;
103 desc
->allocations
= 0;
104 desc
->total_bytes
= 0;
105 desc
->useful_bytes
= 0;
107 struct allocation_blob
*next
= blob
->next
;
108 blob_free(blob
, desc
->chunking
);
113 void *allocate(struct allocator_struct
*desc
, unsigned int size
)
115 unsigned long alignment
= desc
->alignment
;
116 struct allocation_blob
*blob
= desc
->blobs
;
120 desc
->useful_bytes
+= size
;
121 size
= (size
+ alignment
- 1) & ~(alignment
-1);
122 if (!blob
|| blob
->left
< size
) {
123 unsigned int offset
, chunking
= desc
->chunking
;
124 struct allocation_blob
*newblob
= blob_alloc(chunking
);
126 die("out of memory");
127 desc
->total_bytes
+= chunking
;
128 newblob
->next
= blob
;
130 desc
->blobs
= newblob
;
131 offset
= offsetof(struct allocation_blob
, data
);
132 offset
= (offset
+ alignment
- 1) & ~(alignment
-1);
133 blob
->left
= chunking
- offset
;
134 blob
->offset
= offset
- offsetof(struct allocation_blob
, data
);
136 retval
= blob
->data
+ blob
->offset
;
137 blob
->offset
+= size
;
142 static void show_allocations(struct allocator_struct
*x
)
144 fprintf(stderr
, "%s: %d allocations, %d bytes (%d total bytes, "
145 "%6.2f%% usage, %6.2f average size)\n",
146 x
->name
, x
->allocations
, x
->useful_bytes
, x
->total_bytes
,
147 100 * (double) x
->useful_bytes
/ x
->total_bytes
,
148 (double) x
->useful_bytes
/ x
->allocations
);
151 struct allocator_struct ident_allocator
= { "identifiers", NULL
, __alignof__(struct ident
), CHUNK
};
152 struct allocator_struct token_allocator
= { "tokens", NULL
, __alignof__(struct token
), CHUNK
};
153 struct allocator_struct symbol_allocator
= { "symbols", NULL
, __alignof__(struct symbol
), CHUNK
};
154 struct allocator_struct expression_allocator
= { "expressions", NULL
, __alignof__(struct expression
), CHUNK
};
155 struct allocator_struct statement_allocator
= { "statements", NULL
, __alignof__(struct statement
), CHUNK
};
156 struct allocator_struct string_allocator
= { "strings", NULL
, __alignof__(struct statement
), CHUNK
};
157 struct allocator_struct scope_allocator
= { "scopes", NULL
, __alignof__(struct scope
), CHUNK
};
158 struct allocator_struct bytes_allocator
= { "bytes", NULL
, 1, CHUNK
};
159 struct allocator_struct basic_block_allocator
= { "basic_block", NULL
, __alignof__(struct basic_block
), CHUNK
};
160 struct allocator_struct entrypoint_allocator
= { "entrypoint", NULL
, __alignof__(struct entrypoint
), CHUNK
};
161 struct allocator_struct instruction_allocator
= { "instruction", NULL
, __alignof__(struct instruction
), CHUNK
};
162 struct allocator_struct multijmp_allocator
= { "multijmp", NULL
, __alignof__(struct multijmp
), CHUNK
};
163 struct allocator_struct phi_allocator
= { "phi", NULL
, __alignof__(struct phi
), CHUNK
};
164 struct allocator_struct pseudo_allocator
= { "pseudo", NULL
, __alignof__(struct pseudo
), CHUNK
};
166 #define __ALLOCATOR(type, size, x) \
167 type *__alloc_##x(int extra) \
169 return allocate(&x##_allocator, size+extra); \
171 void show_##x##_alloc(void) \
173 show_allocations(&x##_allocator); \
175 void clear_##x##_alloc(void) \
177 drop_all_allocations(&x##_allocator); \
179 #define ALLOCATOR(x) __ALLOCATOR(struct x, sizeof(struct x), x)
181 ALLOCATOR(ident
); ALLOCATOR(token
); ALLOCATOR(symbol
);
182 ALLOCATOR(expression
); ALLOCATOR(statement
); ALLOCATOR(string
);
183 ALLOCATOR(scope
); __ALLOCATOR(void, 0, bytes
);
184 ALLOCATOR(basic_block
); ALLOCATOR(entrypoint
);
185 ALLOCATOR(instruction
);
190 int ptr_list_size(struct ptr_list
*head
)
195 struct ptr_list
*list
= head
;
198 } while ((list
= list
->next
) != head
);
203 void iterate(struct ptr_list
*head
, void (*callback
)(void *, void *, int), void *data
)
205 struct ptr_list
*list
= head
;
206 int flag
= ITERATE_FIRST
;
212 for (i
= 0; i
< list
->nr
; i
++) {
213 if (i
== list
->nr
-1 && list
->next
== head
)
214 flag
|= ITERATE_LAST
;
215 callback(list
->list
[i
], data
, flag
);
219 } while (list
!= head
);
222 void add_ptr_list(struct ptr_list
**listp
, void *ptr
)
224 struct ptr_list
*list
= *listp
;
225 struct ptr_list
*last
= NULL
; /* gcc complains needlessly */
228 if (!list
|| (nr
= (last
= list
->prev
)->nr
) >= LIST_NODE_NR
) {
229 struct ptr_list
*newlist
= malloc(sizeof(*newlist
));
231 die("out of memory for symbol/statement lists");
232 memset(newlist
, 0, sizeof(*newlist
));
234 newlist
->next
= newlist
;
235 newlist
->prev
= newlist
;
238 newlist
->prev
= last
;
239 newlist
->next
= list
;
240 list
->prev
= newlist
;
241 last
->next
= newlist
;
246 last
->list
[nr
] = ptr
;
251 void init_iterator(struct ptr_list
**head
, struct list_iterator
*iterator
, int flags
)
253 iterator
->head
= head
;
255 iterator
->active
= NULL
;
256 iterator
->flags
= flags
;
259 void * next_iterator(struct list_iterator
*iterator
)
261 struct ptr_list
*list
= iterator
->active
;
265 if (*iterator
->head
==NULL
)
268 list
= *iterator
->head
;
270 if (!(iterator
->flags
& ITERATOR_BACKWARDS
)) {
271 iterator
->active
= list
;
272 return list
->list
[0];
276 if (iterator
->flags
& ITERATOR_BACKWARDS
) {
277 index
= iterator
->index
-1;
279 if (list
->prev
== *iterator
->head
)
281 list
= iterator
->active
= list
->prev
;
285 index
= iterator
->index
+ 1;
286 if (index
>= list
->nr
) {
287 if (list
->next
== *iterator
->head
)
289 list
= iterator
->active
= list
->next
;
293 iterator
->index
= index
;
294 return list
->list
[index
];
297 void replace_iterator(struct list_iterator
*iterator
, void* ptr
)
299 struct ptr_list
*list
= iterator
->active
;
301 list
->list
[iterator
->index
] = ptr
;
304 void delete_iterator(struct list_iterator
*iterator
)
306 struct ptr_list
*list
= iterator
->active
;
307 int movsize
= list
->nr
- iterator
->index
- 1;
308 void ** curptr
= list
->list
+iterator
->index
;
311 memmove(curptr
, curptr
+1, movsize
*sizeof curptr
);
314 if (iterator
->flags
& ITERATOR_BACKWARDS
) {
315 if (iterator
->index
+ 1 >= list
->nr
) {
316 iterator
->active
= (list
->next
== *iterator
->head
) ? NULL
: list
->next
;
320 if (--iterator
->index
<0) {
321 iterator
->active
= (list
->prev
== *iterator
->head
) ? NULL
: list
->prev
;
322 iterator
->index
= list
->prev
->nr
;
326 list
->prev
->next
= list
->next
;
327 list
->next
->prev
= list
->prev
;
328 if (list
== *iterator
->head
)
329 *iterator
->head
= (list
->next
== *iterator
->head
) ? NULL
: list
->next
;
334 void init_terminator_iterator(struct instruction
* terminator
, struct terminator_iterator
*iterator
)
336 iterator
->terminator
= terminator
;
340 switch (terminator
->opcode
) {
342 iterator
->branch
= BR_INIT
;
345 case OP_COMPUTEDGOTO
:
346 init_multijmp_iterator(&terminator
->multijmp_list
, &iterator
->multijmp
, 0);
351 struct basic_block
* next_terminator_bb(struct terminator_iterator
*iterator
)
353 struct instruction
*terminator
= iterator
->terminator
;
357 switch (terminator
->opcode
) {
359 switch(iterator
->branch
) {
361 if (terminator
->bb_true
) {
362 iterator
->branch
= BR_TRUE
;
363 return terminator
->bb_true
;
366 if (terminator
->bb_false
) {
367 iterator
->branch
= BR_FALSE
;
368 return terminator
->bb_false
;
371 iterator
->branch
= BR_END
;
375 case OP_COMPUTEDGOTO
:
377 struct multijmp
*jmp
= next_multijmp(&iterator
->multijmp
);
378 return jmp
? jmp
->target
: NULL
;
384 void replace_terminator_bb(struct terminator_iterator
*iterator
, struct basic_block
* bb
)
386 struct instruction
*terminator
= iterator
->terminator
;
390 switch (terminator
->opcode
) {
392 switch(iterator
->branch
) {
394 if (terminator
->bb_true
) {
395 terminator
->bb_true
= bb
;
399 if (terminator
->bb_false
) {
400 terminator
->bb_false
= bb
;
406 case OP_COMPUTEDGOTO
:
408 struct multijmp
*jmp
= (struct multijmp
*) current_iterator(&iterator
->multijmp
);
417 int replace_ptr_list(struct ptr_list
**head
, void *old_ptr
, void *new_ptr
)
420 struct list_iterator iterator
;
423 init_iterator(head
, &iterator
, 0);
424 while ((ptr
=next_iterator(&iterator
)) != NULL
) {
427 replace_iterator(&iterator
, new_ptr
);
429 delete_iterator(&iterator
);
436 void * delete_ptr_list_last(struct ptr_list
**head
)
439 struct ptr_list
*last
, *first
= *head
;
445 ptr
= last
->list
[--last
->nr
];
447 first
->prev
= last
->prev
;
448 last
->prev
->next
= first
;
456 void concat_ptr_list(struct ptr_list
*a
, struct ptr_list
**b
)
459 FOR_EACH_PTR(a
, entry
) {
460 add_ptr_list(b
, entry
);
464 void free_ptr_list(struct ptr_list
**listp
)
466 struct ptr_list
*tmp
, *list
= *listp
;
471 list
->prev
->next
= NULL
;
481 static void do_warn(const char *type
, struct position pos
, const char * fmt
, va_list args
)
483 static char buffer
[512];
486 vsprintf(buffer
, fmt
, args
);
487 name
= input_streams
[pos
.stream
].name
;
489 fprintf(stderr
, "%s:%d:%d: %s%s\n",
490 name
, pos
.line
, pos
.pos
, type
, buffer
);
493 void info(struct position pos
, const char * fmt
, ...)
497 do_warn("", pos
, fmt
, args
);
501 void warn(struct position pos
, const char * fmt
, ...)
503 static int warnings
= 0;
506 if (warnings
> 100) {
510 fmt
= "too many warnings";
515 do_warn("warning: ", pos
, fmt
, args
);
520 void error(struct position pos
, const char * fmt
, ...)
524 do_warn("error: ", pos
, fmt
, args
);
529 void die(const char *fmt
, ...)
532 static char buffer
[512];
535 vsnprintf(buffer
, sizeof(buffer
), fmt
, args
);
538 fprintf(stderr
, "%s\n", buffer
);
542 unsigned int pre_buffer_size
;
543 unsigned char pre_buffer
[8192];
549 void add_pre_buffer(const char *fmt
, ...)
555 size
= pre_buffer_size
;
556 size
+= vsnprintf(pre_buffer
+ size
,
557 sizeof(pre_buffer
) - size
,
559 pre_buffer_size
= size
;
563 char **handle_switch_D(char *arg
, char **next
)
565 const char *name
= arg
+ 1;
566 const char *value
= "1";
572 if (isspace((unsigned char)c
) || c
== '=') {
578 add_pre_buffer("#define %s %s\n", name
, value
);
582 char **handle_switch_E(char *arg
, char **next
)
588 char **handle_switch_v(char *arg
, char **next
)
593 char **handle_switch_I(char *arg
, char **next
)
595 // FIXME: What about "-I-"?
596 if (!strcmp (arg
, "I") && *next
) {
597 add_pre_buffer("#add_include \"%s/\"\n", next
);
598 return next
+ 1; // "-I foo"
600 add_pre_buffer("#add_include \"%s/\"\n", arg
+ 1);
601 return next
; // "-Ifoo" or (bogus) terminal "-I"
605 char **handle_switch_i(char *arg
, char **next
)
607 if (*next
&& !strcmp(arg
, "include")) {
608 char *name
= *++next
;
609 int fd
= open(name
, O_RDONLY
);
619 char **handle_switch_M(char *arg
, char **next
)
621 if (!strcmp(arg
, "MF") || !strcmp(arg
,"MQ") || !strcmp(arg
,"MT")) {
623 die("missing argument for -%s option", arg
);
629 char **handle_switch_m(char *arg
, char **next
)
631 if (!strcmp(arg
, "m64")) {
633 max_int_alignment
= 8;
634 bits_in_pointer
= 64;
635 pointer_alignment
= 8;
640 char **handle_switch_o(char *arg
, char **next
)
642 if (!strcmp (arg
, "o") && *next
)
643 return next
+ 1; // "-o foo"
645 return next
; // "-ofoo" or (bogus) terminal "-o"
648 char **handle_switch(char *arg
, char **next
)
653 case 'D': rc
= handle_switch_D(arg
, next
); break;
654 case 'E': rc
= handle_switch_E(arg
, next
); break;
655 case 'v': rc
= handle_switch_v(arg
, next
); break;
656 case 'I': rc
= handle_switch_I(arg
, next
); break;
657 case 'i': rc
= handle_switch_i(arg
, next
); break;
658 case 'M': rc
= handle_switch_M(arg
, next
); break;
659 case 'm': rc
= handle_switch_m(arg
, next
); break;
660 case 'o': rc
= handle_switch_o(arg
, next
); break;
663 * Ignore unknown command line options:
664 * they're probably gcc switches
671 void create_builtin_stream(void)
673 add_pre_buffer("#define __linux__ 1\n");
674 add_pre_buffer("#define linux linux\n");
675 add_pre_buffer("#define unix 1\n");
676 add_pre_buffer("#define __unix 1\n");
677 add_pre_buffer("#define __unix__ 1\n");
678 add_pre_buffer("#define __STDC__ 1\n");
679 add_pre_buffer("#define __GNUC__ 2\n");
680 add_pre_buffer("#define __GNUC_MINOR__ 95\n");
681 add_pre_buffer("#define __func__ \"function\"\n");
682 add_pre_buffer("#define __extension__\n");
683 add_pre_buffer("#define __pragma__\n");
684 // gcc defines __SIZE_TYPE__ to be size_t. For linux/i86 and
685 // solaris/sparc that is really "unsigned int" and for linux/x86_64
686 // it is "long unsigned int". In either case we can probably
687 // get away with this:
688 add_pre_buffer("#define __SIZE_TYPE__ long unsigned int\n");
689 add_pre_buffer("#define __builtin_stdarg_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
690 add_pre_buffer("#define __builtin_va_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
691 add_pre_buffer("#define __builtin_va_arg(arg,type) ((type)0)\n");
692 add_pre_buffer("#define __builtin_va_end(arg)\n");