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"
29 struct token
*skip_to(struct token
*token
, int op
)
31 while (!match_op(token
, op
) && !eof_token(token
))
36 struct token
*expect(struct token
*token
, int op
, const char *where
)
38 if (!match_op(token
, op
)) {
39 static struct token bad_token
;
40 if (token
!= &bad_token
) {
41 bad_token
.next
= token
;
42 warn(token
->pos
, "Expected %s %s", show_special(op
), where
);
43 warn(token
->pos
, "got %s", show_token(token
));
46 return skip_to(token
, op
);
52 unsigned int hexval(unsigned int c
)
60 retval
= c
- 'a' + 10;
63 retval
= c
- 'A' + 10;
70 * Simple allocator for data that doesn't get partially free'd.
71 * The tokenizer and parser allocate a _lot_ of small data structures
72 * (often just two-three bytes for things like small integers),
73 * and since they all depend on each other you can't free them
74 * individually _anyway_. So do something that is very space-
75 * efficient: allocate larger "blobs", and give out individual
76 * small bits and pieces of it with no maintenance overhead.
78 struct allocation_blob
{
79 struct allocation_blob
*next
;
80 unsigned int left
, offset
;
85 #define blob_alloc(size) mmap(NULL, ((size)+4095) & ~4095, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)
86 #define blob_free(addr,size) munmap((addr), ((size)+4095) & ~4095)
88 struct allocator_struct
{
90 struct allocation_blob
*blobs
;
91 unsigned int alignment
;
92 unsigned int chunking
;
94 unsigned int allocations
, total_bytes
, useful_bytes
;
97 void drop_all_allocations(struct allocator_struct
*desc
)
99 struct allocation_blob
*blob
= desc
->blobs
;
102 desc
->allocations
= 0;
103 desc
->total_bytes
= 0;
104 desc
->useful_bytes
= 0;
106 struct allocation_blob
*next
= blob
->next
;
107 blob_free(blob
, desc
->chunking
);
112 void *allocate(struct allocator_struct
*desc
, unsigned int size
)
114 unsigned long alignment
= desc
->alignment
;
115 struct allocation_blob
*blob
= desc
->blobs
;
119 desc
->useful_bytes
+= size
;
120 size
= (size
+ alignment
- 1) & ~(alignment
-1);
121 if (!blob
|| blob
->left
< size
) {
122 unsigned int offset
, chunking
= desc
->chunking
;
123 struct allocation_blob
*newblob
= blob_alloc(chunking
);
125 die("out of memory");
126 desc
->total_bytes
+= chunking
;
127 newblob
->next
= blob
;
129 desc
->blobs
= newblob
;
130 offset
= offsetof(struct allocation_blob
, data
);
131 if (alignment
> offset
)
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
;
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 init_multijmp_iterator(&terminator
->multijmp_list
, &iterator
->multijmp
, 0);
350 struct basic_block
* next_terminator_bb(struct terminator_iterator
*iterator
)
352 struct instruction
*terminator
= iterator
->terminator
;
356 switch (terminator
->opcode
) {
358 switch(iterator
->branch
) {
360 if (terminator
->bb_true
) {
361 iterator
->branch
= BR_TRUE
;
362 return terminator
->bb_true
;
365 if (terminator
->bb_false
) {
366 iterator
->branch
= BR_FALSE
;
367 return terminator
->bb_false
;
370 iterator
->branch
= BR_END
;
375 struct multijmp
*jmp
= next_multijmp(&iterator
->multijmp
);
376 return jmp
? jmp
->target
: NULL
;
382 void replace_terminator_bb(struct terminator_iterator
*iterator
, struct basic_block
* bb
)
384 struct instruction
*terminator
= iterator
->terminator
;
388 switch (terminator
->opcode
) {
390 switch(iterator
->branch
) {
392 if (terminator
->bb_true
) {
393 terminator
->bb_true
= bb
;
397 if (terminator
->bb_false
) {
398 terminator
->bb_false
= bb
;
405 struct multijmp
*jmp
= (struct multijmp
*) current_iterator(&iterator
->multijmp
);
414 int replace_ptr_list(struct ptr_list
**head
, void *old_ptr
, void *new_ptr
)
417 struct list_iterator iterator
;
420 init_iterator(head
, &iterator
, 0);
421 while ((ptr
=next_iterator(&iterator
))) {
424 replace_iterator(&iterator
, new_ptr
);
426 delete_iterator(&iterator
);
433 void * delete_ptr_list_last(struct ptr_list
**head
)
436 struct ptr_list
*last
;
440 last
= (*head
)->prev
;
442 ptr
= last
->list
[--last
->nr
];
451 void concat_ptr_list(struct ptr_list
*a
, struct ptr_list
**b
)
454 FOR_EACH_PTR(a
, entry
) {
455 add_ptr_list(b
, entry
);
459 void free_ptr_list(struct ptr_list
**listp
)
461 struct ptr_list
*tmp
, *list
= *listp
;
466 list
->prev
->next
= NULL
;
476 static void do_warn(const char *type
, struct position pos
, const char * fmt
, va_list args
)
478 static char buffer
[512];
481 vsprintf(buffer
, fmt
, args
);
482 name
= input_streams
[pos
.stream
].name
;
484 fprintf(stderr
, "%s: %s:%d:%d: %s\n",
485 type
, name
, pos
.line
, pos
.pos
, buffer
);
488 void warn(struct position pos
, const char * fmt
, ...)
490 static int warnings
= 0;
493 if (warnings
> 100) {
497 fmt
= "too many warnings";
502 do_warn("warning", pos
, fmt
, args
);
507 void error(struct position pos
, const char * fmt
, ...)
511 do_warn("error", pos
, fmt
, args
);
516 void die(const char *fmt
, ...)
519 static char buffer
[512];
522 vsnprintf(buffer
, sizeof(buffer
), fmt
, args
);
525 fprintf(stderr
, "%s\n", buffer
);
529 unsigned int pre_buffer_size
;
530 unsigned char pre_buffer
[8192];
536 void add_pre_buffer(const char *fmt
, ...)
542 size
= pre_buffer_size
;
543 size
+= vsnprintf(pre_buffer
+ size
,
544 sizeof(pre_buffer
) - size
,
546 pre_buffer_size
= size
;
550 char **handle_switch_D(char *arg
, char **next
)
552 const char *name
= arg
+ 1;
553 const char *value
= "";
559 if (isspace(c
) || c
== '=') {
565 add_pre_buffer("#define %s %s\n", name
, value
);
569 char **handle_switch_E(char *arg
, char **next
)
575 char **handle_switch_v(char *arg
, char **next
)
580 char **handle_switch_I(char *arg
, char **next
)
582 add_pre_buffer("#add_include \"%s/\"\n", arg
+ 1);
586 char **handle_switch_i(char *arg
, char **next
)
588 if (*next
&& !strcmp(arg
, "include")) {
589 char *name
= *++next
;
590 int fd
= open(name
, O_RDONLY
);
600 char **handle_switch(char *arg
, char **next
)
605 case 'D': rc
= handle_switch_D(arg
, next
); break;
606 case 'E': rc
= handle_switch_E(arg
, next
); break;
607 case 'v': rc
= handle_switch_v(arg
, next
); break;
608 case 'I': rc
= handle_switch_I(arg
, next
); break;
609 case 'i': rc
= handle_switch_i(arg
, next
); break;
612 * Ignore unknown command line options:
613 * they're probably gcc switches
620 void create_builtin_stream(void)
622 add_pre_buffer("#define __i386__ 1\n");
623 add_pre_buffer("#define __linux__ 1\n");
624 add_pre_buffer("#define __STDC__ 1\n");
625 add_pre_buffer("#define linux linux\n");
626 add_pre_buffer("#define cond_syscall(x)\n");
627 add_pre_buffer("#define __GNUC__ 2\n");
628 add_pre_buffer("#define __GNUC_MINOR__ 95\n");
629 add_pre_buffer("#define __func__ \"function\"\n");
630 add_pre_buffer("#define __extension__\n");
631 add_pre_buffer("#define __pragma__\n");
632 add_pre_buffer("#define __builtin_stdarg_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
633 add_pre_buffer("#define __builtin_va_arg(arg,type) ((type)0)\n");
634 add_pre_buffer("#define __builtin_va_end(arg)\n");