1/*
2 * Linearize - walk the statement tree (but _not_ the expressions)
3 * to generate a linear version of it and the basic blocks.
4 *
5 * NOTE! We're not interested in the actual sub-expressions yet,
6 * even though they can generate conditional branches and
7 * subroutine calls. That's all "local" behaviour.
8 *
9 * Copyright (C) 2004 Linus Torvalds
10 * Copyright (C) 2004 Christopher Li
11 */
12
13#include <string.h>
14#include <stdarg.h>
15#include <stdlib.h>
16#include <stdio.h>
17#include <assert.h>
18
19#include "parse.h"
20#include "expression.h"
21#include "linearize.h"
22#include "optimize.h"
23#include "flow.h"
24#include "target.h"
25
26static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt);
27static pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr);
28
29static pseudo_t add_cast(struct entrypoint *ep, struct symbol *to, struct symbol *from, int op, pseudo_t src);
30static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right);
31static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val);
32static pseudo_t linearize_one_symbol(struct entrypoint *ep, struct symbol *sym);
33
34struct access_data;
35static pseudo_t add_load(struct entrypoint *ep, struct access_data *);
36static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *);
37static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *from, struct symbol *to);
38
39struct pseudo void_pseudo = {};
40
41static struct position current_pos;
42
43ALLOCATOR(pseudo_user, "pseudo_user");
44
45static struct instruction *alloc_instruction(int opcode, int size)
46{
47	struct instruction * insn = __alloc_instruction(0);
48	insn->opcode = opcode;
49	insn->size = size;
50	insn->pos = current_pos;
51	return insn;
52}
53
54static inline int type_size(struct symbol *type)
55{
56	return type ? type->bit_size > 0 ? type->bit_size : 0 : 0;
57}
58
59static struct instruction *alloc_typed_instruction(int opcode, struct symbol *type)
60{
61	struct instruction *insn = alloc_instruction(opcode, type_size(type));
62	insn->type = type;
63	return insn;
64}
65
66static struct entrypoint *alloc_entrypoint(void)
67{
68	return __alloc_entrypoint(0);
69}
70
71static struct basic_block *alloc_basic_block(struct entrypoint *ep, struct position pos)
72{
73	static int nr;
74	struct basic_block *bb = __alloc_basic_block(0);
75	bb->pos = pos;
76	bb->ep = ep;
77	bb->nr = nr++;
78	return bb;
79}
80
81static struct multijmp *alloc_multijmp(struct basic_block *target, long long begin, long long end)
82{
83	struct multijmp *multijmp = __alloc_multijmp(0);
84	multijmp->target = target;
85	multijmp->begin = begin;
86	multijmp->end = end;
87	return multijmp;
88}
89
90const char *show_label(struct basic_block *bb)
91{
92	static int n;
93	static char buffer[4][16];
94	char *buf = buffer[3 & ++n];
95
96	if (!bb)
97		return ".L???";
98	snprintf(buf, 64, ".L%u", bb->nr);
99	return buf;
100}
101
102const char *show_pseudo(pseudo_t pseudo)
103{
104	static int n;
105	static char buffer[4][64];
106	char *buf;
107	int i;
108
109	if (!pseudo)
110		return "no pseudo";
111	if (pseudo == VOID)
112		return "VOID";
113	buf = buffer[3 & ++n];
114	switch(pseudo->type) {
115	case PSEUDO_SYM: {
116		struct symbol *sym = pseudo->sym;
117		struct expression *expr;
118
119		if (!sym) {
120			snprintf(buf, 64, "<bad symbol>");
121			break;
122		}
123		if (sym->bb_target) {
124			snprintf(buf, 64, "%s", show_label(sym->bb_target));
125			break;
126		}
127		if (sym->ident) {
128			snprintf(buf, 64, "%s", show_ident(sym->ident));
129			break;
130		}
131		expr = sym->initializer;
132		snprintf(buf, 64, "<anon symbol:%p>", verbose ? sym : NULL);
133		if (expr) {
134			switch (expr->type) {
135			case EXPR_VALUE:
136				snprintf(buf, 64, "<symbol value: %lld>", expr->value);
137				break;
138			case EXPR_STRING:
139				return show_string(expr->string);
140			default:
141				break;
142			}
143		}
144		break;
145	}
146	case PSEUDO_REG:
147		i = snprintf(buf, 64, "%%r%d", pseudo->nr);
148		if (pseudo->ident)
149			sprintf(buf+i, "(%s)", show_ident(pseudo->ident));
150		break;
151	case PSEUDO_VAL: {
152		long long value = pseudo->value;
153		if (value > 1000 || value < -1000)
154			snprintf(buf, 64, "$%#llx", value);
155		else
156			snprintf(buf, 64, "$%lld", value);
157		break;
158	}
159	case PSEUDO_ARG:
160		snprintf(buf, 64, "%%arg%d", pseudo->nr);
161		break;
162	case PSEUDO_PHI:
163		i = snprintf(buf, 64, "%%phi%d", pseudo->nr);
164		if (pseudo->ident)
165			sprintf(buf+i, "(%s)", show_ident(pseudo->ident));
166		break;
167	case PSEUDO_UNDEF:
168		return "UNDEF";
169	default:
170		snprintf(buf, 64, "<bad pseudo type %d>", pseudo->type);
171	}
172	return buf;
173}
174
175static const char *opcodes[] = {
176	[OP_BADOP] = "bad_op",
177
178	/* Fn entrypoint */
179	[OP_ENTRY] = "<entry-point>",
180
181	/* Terminator */
182	[OP_RET] = "ret",
183	[OP_BR] = "br",
184	[OP_CBR] = "cbr",
185	[OP_SWITCH] = "switch",
186	[OP_COMPUTEDGOTO] = "jmp *",
187
188	/* Binary */
189	[OP_ADD] = "add",
190	[OP_SUB] = "sub",
191	[OP_MUL] = "mul",
192	[OP_DIVU] = "divu",
193	[OP_DIVS] = "divs",
194	[OP_MODU] = "modu",
195	[OP_MODS] = "mods",
196	[OP_SHL] = "shl",
197	[OP_LSR] = "lsr",
198	[OP_ASR] = "asr",
199
200	/* Floating-point Binary */
201	[OP_FADD] = "fadd",
202	[OP_FSUB] = "fsub",
203	[OP_FMUL] = "fmul",
204	[OP_FDIV] = "fdiv",
205
206	/* Logical */
207	[OP_AND] = "and",
208	[OP_OR] = "or",
209	[OP_XOR] = "xor",
210
211	/* Binary comparison */
212	[OP_SET_EQ] = "seteq",
213	[OP_SET_NE] = "setne",
214	[OP_SET_LE] = "setle",
215	[OP_SET_GE] = "setge",
216	[OP_SET_LT] = "setlt",
217	[OP_SET_GT] = "setgt",
218	[OP_SET_B] = "setb",
219	[OP_SET_A] = "seta",
220	[OP_SET_BE] = "setbe",
221	[OP_SET_AE] = "setae",
222
223	/* floating-point comparison */
224	[OP_FCMP_ORD] = "fcmpord",
225	[OP_FCMP_OEQ] = "fcmpoeq",
226	[OP_FCMP_ONE] = "fcmpone",
227	[OP_FCMP_OLE] = "fcmpole",
228	[OP_FCMP_OGE] = "fcmpoge",
229	[OP_FCMP_OLT] = "fcmpolt",
230	[OP_FCMP_OGT] = "fcmpogt",
231	[OP_FCMP_UEQ] = "fcmpueq",
232	[OP_FCMP_UNE] = "fcmpune",
233	[OP_FCMP_ULE] = "fcmpule",
234	[OP_FCMP_UGE] = "fcmpuge",
235	[OP_FCMP_ULT] = "fcmpult",
236	[OP_FCMP_UGT] = "fcmpugt",
237	[OP_FCMP_UNO] = "fcmpuno",
238
239	/* Uni */
240	[OP_NOT] = "not",
241	[OP_NEG] = "neg",
242	[OP_FNEG] = "fneg",
243
244	/* Special three-input */
245	[OP_SEL] = "select",
246
247	/* Memory */
248	[OP_LOAD] = "load",
249	[OP_STORE] = "store",
250	[OP_SETVAL] = "set",
251	[OP_SETFVAL] = "setfval",
252	[OP_SYMADDR] = "symaddr",
253
254	/* Other */
255	[OP_PHI] = "phi",
256	[OP_PHISOURCE] = "phisrc",
257	[OP_SEXT] = "sext",
258	[OP_ZEXT] = "zext",
259	[OP_TRUNC] = "trunc",
260	[OP_FCVTU] = "fcvtu",
261	[OP_FCVTS] = "fcvts",
262	[OP_UCVTF] = "ucvtf",
263	[OP_SCVTF] = "scvtf",
264	[OP_FCVTF] = "fcvtf",
265	[OP_UTPTR] = "utptr",
266	[OP_PTRTU] = "ptrtu",
267	[OP_PTRCAST] = "ptrcast",
268	[OP_INLINED_CALL] = "# call",
269	[OP_CALL] = "call",
270	[OP_SLICE] = "slice",
271	[OP_NOP] = "nop",
272	[OP_DEATHNOTE] = "dead",
273	[OP_ASM] = "asm",
274
275	/* Sparse tagging (line numbers, context, whatever) */
276	[OP_CONTEXT] = "context",
277	[OP_RANGE] = "range-check",
278
279	[OP_COPY] = "copy",
280};
281
282static char *show_asm_constraints(char *buf, const char *sep, struct asm_constraint_list *list)
283{
284	struct asm_constraint *entry;
285
286	FOR_EACH_PTR(list, entry) {
287		buf += sprintf(buf, "%s\"%s\"", sep, entry->constraint);
288		if (entry->pseudo)
289			buf += sprintf(buf, " (%s)", show_pseudo(entry->pseudo));
290		if (entry->ident)
291			buf += sprintf(buf, " [%s]", show_ident(entry->ident));
292		sep = ", ";
293	} END_FOR_EACH_PTR(entry);
294	return buf;
295}
296
297static char *show_asm(char *buf, struct instruction *insn)
298{
299	struct asm_rules *rules = insn->asm_rules;
300
301	buf += sprintf(buf, "\"%s\"", insn->string);
302	buf = show_asm_constraints(buf, "\n\t\tout: ", rules->outputs);
303	buf = show_asm_constraints(buf, "\n\t\tin: ", rules->inputs);
304	buf = show_asm_constraints(buf, "\n\t\tclobber: ", rules->clobbers);
305	return buf;
306}
307
308const char *show_instruction(struct instruction *insn)
309{
310	int opcode = insn->opcode;
311	static char buffer[4096];
312	char *buf;
313
314	buf = buffer;
315	if (!insn->bb)
316		buf += sprintf(buf, "# ");
317
318	if (opcode < ARRAY_SIZE(opcodes)) {
319		const char *op = opcodes[opcode];
320		if (!op)
321			buf += sprintf(buf, "opcode:%d", opcode);
322		else
323			buf += sprintf(buf, "%s", op);
324		if (insn->size)
325			buf += sprintf(buf, ".%d", insn->size);
326		memset(buf, ' ', 20);
327		buf++;
328	}
329
330	if (buf < buffer + 12)
331		buf = buffer + 12;
332	switch (opcode) {
333	case OP_RET:
334		if (insn->src && insn->src != VOID)
335			buf += sprintf(buf, "%s", show_pseudo(insn->src));
336		break;
337
338	case OP_CBR:
339		buf += sprintf(buf, "%s, %s, %s", show_pseudo(insn->cond), show_label(insn->bb_true), show_label(insn->bb_false));
340		break;
341
342	case OP_BR:
343		buf += sprintf(buf, "%s", show_label(insn->bb_true));
344		break;
345
346	case OP_SETVAL: {
347		struct expression *expr = insn->val;
348		buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
349
350		if (!expr) {
351			buf += sprintf(buf, "%s", "<none>");
352			break;
353		}
354
355		switch (expr->type) {
356		case EXPR_VALUE:
357			buf += sprintf(buf, "%lld", expr->value);
358			break;
359		case EXPR_FVALUE:
360			buf += sprintf(buf, "%Le", expr->fvalue);
361			break;
362		case EXPR_STRING:
363			buf += sprintf(buf, "%.40s", show_string(expr->string));
364			break;
365		case EXPR_SYMBOL:
366			buf += sprintf(buf, "%s", show_ident(expr->symbol->ident));
367			break;
368		case EXPR_LABEL:
369			buf += sprintf(buf, "%s", show_label(expr->symbol->bb_target));
370			break;
371		default:
372			buf += sprintf(buf, "SETVAL EXPR TYPE %d", expr->type);
373		}
374		break;
375	}
376	case OP_SETFVAL:
377		buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
378		buf += sprintf(buf, "%Le", insn->fvalue);
379		break;
380
381	case OP_SWITCH: {
382		struct multijmp *jmp;
383		buf += sprintf(buf, "%s", show_pseudo(insn->cond));
384		FOR_EACH_PTR(insn->multijmp_list, jmp) {
385			if (jmp->begin == jmp->end)
386				buf += sprintf(buf, ", %lld -> %s", jmp->begin, show_label(jmp->target));
387			else if (jmp->begin < jmp->end)
388				buf += sprintf(buf, ", %lld ... %lld -> %s", jmp->begin, jmp->end, show_label(jmp->target));
389			else
390				buf += sprintf(buf, ", default -> %s", show_label(jmp->target));
391		} END_FOR_EACH_PTR(jmp);
392		break;
393	}
394	case OP_COMPUTEDGOTO: {
395		struct multijmp *jmp;
396		buf += sprintf(buf, "%s", show_pseudo(insn->src));
397		FOR_EACH_PTR(insn->multijmp_list, jmp) {
398			buf += sprintf(buf, ", %s", show_label(jmp->target));
399		} END_FOR_EACH_PTR(jmp);
400		break;
401	}
402
403	case OP_PHISOURCE: {
404		struct instruction *phi;
405		buf += sprintf(buf, "%s <- %s    ", show_pseudo(insn->target), show_pseudo(insn->phi_src));
406		FOR_EACH_PTR(insn->phi_users, phi) {
407			buf += sprintf(buf, " (%s)", show_pseudo(phi->target));
408		} END_FOR_EACH_PTR(phi);
409		break;
410	}
411
412	case OP_PHI: {
413		pseudo_t phi;
414		const char *s = " <-";
415		buf += sprintf(buf, "%s", show_pseudo(insn->target));
416		FOR_EACH_PTR(insn->phi_list, phi) {
417			if (phi == VOID && !verbose)
418				continue;
419			buf += sprintf(buf, "%s %s", s, show_pseudo(phi));
420			s = ",";
421		} END_FOR_EACH_PTR(phi);
422		break;
423	}
424	case OP_LOAD:
425		buf += sprintf(buf, "%s <- %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
426		break;
427	case OP_STORE:
428		buf += sprintf(buf, "%s -> %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
429		break;
430	case OP_INLINED_CALL:
431	case OP_CALL: {
432		struct pseudo *arg;
433		if (insn->target && insn->target != VOID)
434			buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
435		buf += sprintf(buf, "%s", show_pseudo(insn->func));
436		FOR_EACH_PTR(insn->arguments, arg) {
437			buf += sprintf(buf, ", %s", show_pseudo(arg));
438		} END_FOR_EACH_PTR(arg);
439		break;
440	}
441	case OP_SEXT: case OP_ZEXT:
442	case OP_TRUNC:
443	case OP_FCVTU: case OP_FCVTS:
444	case OP_UCVTF: case OP_SCVTF:
445	case OP_FCVTF:
446	case OP_UTPTR:
447	case OP_PTRTU:
448	case OP_PTRCAST:
449		buf += sprintf(buf, "%s <- (%d) %s",
450			show_pseudo(insn->target),
451			type_size(insn->orig_type),
452			show_pseudo(insn->src));
453		break;
454	case OP_BINARY ... OP_BINARY_END:
455	case OP_FPCMP ... OP_FPCMP_END:
456	case OP_BINCMP ... OP_BINCMP_END:
457		buf += sprintf(buf, "%s <- %s, %s", show_pseudo(insn->target), show_pseudo(insn->src1), show_pseudo(insn->src2));
458		break;
459
460	case OP_SEL:
461		buf += sprintf(buf, "%s <- %s, %s, %s", show_pseudo(insn->target),
462			show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));
463		break;
464
465	case OP_SLICE:
466		buf += sprintf(buf, "%s <- %s, %d, %d", show_pseudo(insn->target), show_pseudo(insn->base), insn->from, insn->len);
467		break;
468
469	case OP_NOT: case OP_NEG:
470	case OP_FNEG:
471	case OP_SYMADDR:
472		buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
473		break;
474
475	case OP_CONTEXT:
476		buf += sprintf(buf, "%s%d", insn->check ? "check: " : "", insn->increment);
477		break;
478	case OP_RANGE:
479		buf += sprintf(buf, "%s between %s..%s", show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));
480		break;
481	case OP_NOP:
482		buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
483		break;
484	case OP_DEATHNOTE:
485		buf += sprintf(buf, "%s", show_pseudo(insn->target));
486		break;
487	case OP_ASM:
488		buf = show_asm(buf, insn);
489		break;
490	case OP_COPY:
491		buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src));
492		break;
493	default:
494		break;
495	}
496
497	if (buf >= buffer + sizeof(buffer))
498		die("instruction buffer overflowed %td\n", buf - buffer);
499	do { --buf; } while (*buf == ' ');
500	*++buf = 0;
501	return buffer;
502}
503
504void show_bb(struct basic_block *bb)
505{
506	struct instruction *insn;
507
508	printf("%s:\n", show_label(bb));
509	if (verbose) {
510		pseudo_t needs, defines;
511		printf("%s:%d\n", stream_name(bb->pos.stream), bb->pos.line);
512
513		FOR_EACH_PTR(bb->needs, needs) {
514			struct instruction *def = needs->def;
515			if (def->opcode != OP_PHI) {
516				printf("  **uses %s (from %s)**\n", show_pseudo(needs), show_label(def->bb));
517			} else {
518				pseudo_t phi;
519				const char *sep = " ";
520				printf("  **uses %s (from", show_pseudo(needs));
521				FOR_EACH_PTR(def->phi_list, phi) {
522					if (phi == VOID)
523						continue;
524					printf("%s(%s:%s)", sep, show_pseudo(phi), show_label(phi->def->bb));
525					sep = ", ";
526				} END_FOR_EACH_PTR(phi);
527				printf(")**\n");
528			}
529		} END_FOR_EACH_PTR(needs);
530
531		FOR_EACH_PTR(bb->defines, defines) {
532			printf("  **defines %s **\n", show_pseudo(defines));
533		} END_FOR_EACH_PTR(defines);
534
535		if (bb->parents) {
536			struct basic_block *from;
537			FOR_EACH_PTR(bb->parents, from) {
538				printf("  **from %s (%s:%d:%d)**\n", show_label(from),
539					stream_name(from->pos.stream), from->pos.line, from->pos.pos);
540			} END_FOR_EACH_PTR(from);
541		}
542
543		if (bb->children) {
544			struct basic_block *to;
545			FOR_EACH_PTR(bb->children, to) {
546				printf("  **to %s (%s:%d:%d)**\n", show_label(to),
547					stream_name(to->pos.stream), to->pos.line, to->pos.pos);
548			} END_FOR_EACH_PTR(to);
549		}
550	}
551
552	FOR_EACH_PTR(bb->insns, insn) {
553		if (!insn->bb && verbose < 2)
554			continue;
555		printf("\t%s\n", show_instruction(insn));
556	} END_FOR_EACH_PTR(insn);
557	if (!bb_terminated(bb))
558		printf("\tEND\n");
559}
560
561static void show_symbol_usage(pseudo_t pseudo)
562{
563	struct pseudo_user *pu;
564
565	if (pseudo) {
566		FOR_EACH_PTR(pseudo->users, pu) {
567			printf("\t%s\n", show_instruction(pu->insn));
568		} END_FOR_EACH_PTR(pu);
569	}
570}
571
572void show_entry(struct entrypoint *ep)
573{
574	struct symbol *sym;
575	struct basic_block *bb;
576
577	printf("%s:\n", show_ident(ep->name->ident));
578
579	if (verbose) {
580		printf("ep %p: %s\n", ep, show_ident(ep->name->ident));
581
582		FOR_EACH_PTR(ep->syms, sym) {
583			if (!sym->pseudo)
584				continue;
585			if (!sym->pseudo->users)
586				continue;
587			printf("   sym: %p %s\n", sym, show_ident(sym->ident));
588			if (sym->ctype.modifiers & (MOD_EXTERN | MOD_STATIC | MOD_ADDRESSABLE))
589				printf("\texternal visibility\n");
590			show_symbol_usage(sym->pseudo);
591		} END_FOR_EACH_PTR(sym);
592
593		printf("\n");
594	}
595
596	FOR_EACH_PTR(ep->bbs, bb) {
597		if (!bb)
598			continue;
599		if (!bb->parents && !bb->children && !bb->insns && verbose < 2)
600			continue;
601		show_bb(bb);
602		printf("\n");
603	} END_FOR_EACH_PTR(bb);
604
605	printf("\n");
606}
607
608static void bind_label(struct symbol *label, struct basic_block *bb, struct position pos)
609{
610	if (label->bb_target)
611		warning(pos, "label '%s' already bound", show_ident(label->ident));
612	label->bb_target = bb;
613}
614
615static struct basic_block * get_bound_block(struct entrypoint *ep, struct symbol *label)
616{
617	struct basic_block *bb = label->bb_target;
618
619	if (!bb) {
620		bb = alloc_basic_block(ep, label->pos);
621		label->bb_target = bb;
622	}
623	return bb;
624}
625
626static void finish_block(struct entrypoint *ep)
627{
628	struct basic_block *src = ep->active;
629	if (bb_reachable(src))
630		ep->active = NULL;
631}
632
633static void add_goto(struct entrypoint *ep, struct basic_block *dst)
634{
635	struct basic_block *src = ep->active;
636	if (bb_reachable(src)) {
637		struct instruction *br = alloc_instruction(OP_BR, 0);
638		br->bb_true = dst;
639		add_bb(&dst->parents, src);
640		add_bb(&src->children, dst);
641		br->bb = src;
642		add_instruction(&src->insns, br);
643		ep->active = NULL;
644	}
645}
646
647static void add_one_insn(struct entrypoint *ep, struct instruction *insn)
648{
649	struct basic_block *bb = ep->active;
650
651	if (bb_reachable(bb)) {
652		insn->bb = bb;
653		add_instruction(&bb->insns, insn);
654	}
655}
656
657static void set_activeblock(struct entrypoint *ep, struct basic_block *bb)
658{
659	if (!bb_terminated(ep->active))
660		add_goto(ep, bb);
661
662	ep->active = bb;
663	if (bb_reachable(bb))
664		add_bb(&ep->bbs, bb);
665}
666
667static void remove_parent(struct basic_block *child, struct basic_block *parent)
668{
669	remove_bb_from_list(&child->parents, parent, 1);
670	if (!child->parents)
671		repeat_phase |= REPEAT_CFG_CLEANUP;
672}
673
674/* Change a "switch" or a conditional branch into a branch */
675void insert_branch(struct basic_block *bb, struct instruction *jmp, struct basic_block *target)
676{
677	struct instruction *br, *old;
678	struct basic_block *child;
679
680	/* Remove the switch */
681	old = delete_last_instruction(&bb->insns);
682	assert(old == jmp);
683	kill_instruction(old);
684
685	br = alloc_instruction(OP_BR, 0);
686	br->bb = bb;
687	br->bb_true = target;
688	add_instruction(&bb->insns, br);
689
690	FOR_EACH_PTR(bb->children, child) {
691		if (child == target) {
692			target = NULL;	/* Trigger just once */
693			continue;
694		}
695		DELETE_CURRENT_PTR(child);
696		remove_parent(child, bb);
697	} END_FOR_EACH_PTR(child);
698	PACK_PTR_LIST(&bb->children);
699}
700
701
702void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi_node, pseudo_t if_true, pseudo_t if_false)
703{
704	pseudo_t target;
705	struct instruction *select;
706
707	/* Remove the 'br' */
708	delete_last_instruction(&bb->insns);
709
710	select = alloc_typed_instruction(OP_SEL, phi_node->type);
711	select->bb = bb;
712
713	assert(br->cond);
714	use_pseudo(select, br->cond, &select->src1);
715
716	target = phi_node->target;
717	assert(target->def == phi_node);
718	select->target = target;
719	target->def = select;
720
721	use_pseudo(select, if_true, &select->src2);
722	use_pseudo(select, if_false, &select->src3);
723
724	add_instruction(&bb->insns, select);
725	add_instruction(&bb->insns, br);
726}
727
728static inline int bb_empty(struct basic_block *bb)
729{
730	return !bb->insns;
731}
732
733/* Add a label to the currently active block, return new active block */
734static struct basic_block * add_label(struct entrypoint *ep, struct symbol *label)
735{
736	struct basic_block *bb = label->bb_target;
737
738	if (bb) {
739		set_activeblock(ep, bb);
740		return bb;
741	}
742	bb = ep->active;
743	if (!bb_reachable(bb) || !bb_empty(bb)) {
744		bb = alloc_basic_block(ep, label->pos);
745		set_activeblock(ep, bb);
746	}
747	label->bb_target = bb;
748	return bb;
749}
750
751static void add_branch(struct entrypoint *ep, pseudo_t cond, struct basic_block *bb_true, struct basic_block *bb_false)
752{
753	struct basic_block *bb = ep->active;
754	struct instruction *br;
755
756	if (bb_reachable(bb)) {
757		br = alloc_instruction(OP_CBR, 0);
758		use_pseudo(br, cond, &br->cond);
759		br->bb_true = bb_true;
760		br->bb_false = bb_false;
761		add_bb(&bb_true->parents, bb);
762		add_bb(&bb_false->parents, bb);
763		add_bb(&bb->children, bb_true);
764		add_bb(&bb->children, bb_false);
765		add_one_insn(ep, br);
766	}
767}
768
769pseudo_t alloc_pseudo(struct instruction *def)
770{
771	static int nr = 0;
772	struct pseudo * pseudo = __alloc_pseudo(0);
773	pseudo->type = PSEUDO_REG;
774	pseudo->nr = ++nr;
775	pseudo->def = def;
776	return pseudo;
777}
778
779static pseudo_t symbol_pseudo(struct entrypoint *ep, struct symbol *sym)
780{
781	pseudo_t pseudo;
782
783	if (!sym)
784		return VOID;
785
786	pseudo = sym->pseudo;
787	if (!pseudo) {
788		pseudo = __alloc_pseudo(0);
789		pseudo->nr = -1;
790		pseudo->type = PSEUDO_SYM;
791		pseudo->sym = sym;
792		pseudo->ident = sym->ident;
793		sym->pseudo = pseudo;
794		add_pseudo(&ep->accesses, pseudo);
795	}
796	/* Symbol pseudos have neither nr nor def */
797	return pseudo;
798}
799
800pseudo_t value_pseudo(long long val)
801{
802#define MAX_VAL_HASH 64
803	static struct pseudo_list *prev[MAX_VAL_HASH];
804	int hash = val & (MAX_VAL_HASH-1);
805	struct pseudo_list **list = prev + hash;
806	pseudo_t pseudo;
807
808	FOR_EACH_PTR(*list, pseudo) {
809		if (pseudo->value == val)
810			return pseudo;
811	} END_FOR_EACH_PTR(pseudo);
812
813	pseudo = __alloc_pseudo(0);
814	pseudo->type = PSEUDO_VAL;
815	pseudo->value = val;
816	add_pseudo(list, pseudo);
817
818	/* Value pseudos have neither nr, usage nor def */
819	return pseudo;
820}
821
822pseudo_t undef_pseudo(void)
823{
824	pseudo_t pseudo = __alloc_pseudo(0);
825	pseudo->type = PSEUDO_UNDEF;
826	return pseudo;
827}
828
829static pseudo_t argument_pseudo(struct entrypoint *ep, int nr)
830{
831	pseudo_t pseudo = __alloc_pseudo(0);
832	struct instruction *entry = ep->entry;
833
834	pseudo->type = PSEUDO_ARG;
835	pseudo->nr = nr;
836	pseudo->def = entry;
837	add_pseudo(&entry->arg_list, pseudo);
838
839	/* Argument pseudos have neither usage nor def */
840	return pseudo;
841}
842
843struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type)
844{
845	struct instruction *insn = alloc_typed_instruction(OP_PHISOURCE, type);
846	pseudo_t phi = __alloc_pseudo(0);
847	static int nr = 0;
848
849	phi->type = PSEUDO_PHI;
850	phi->nr = ++nr;
851	phi->def = insn;
852
853	use_pseudo(insn, pseudo, &insn->phi_src);
854	insn->target = phi;
855	return insn;
856}
857
858pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type)
859{
860	struct instruction *insn;
861
862	if (!source)
863		return VOID;
864
865	insn = alloc_phisrc(pseudo, type);
866	insn->bb = source;
867	add_instruction(&source->insns, insn);
868	return insn->target;
869}
870
871struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident)
872{
873	struct instruction *phi_node = alloc_typed_instruction(OP_PHI, type);
874	pseudo_t phi;
875
876	phi = alloc_pseudo(phi_node);
877	phi->ident = ident;
878	phi->def = phi_node;
879	phi_node->target = phi;
880	phi_node->bb = bb;
881	return phi_node;
882}
883
884void add_phi_node(struct basic_block *bb, struct instruction *phi_node)
885{
886	struct instruction *insn;
887
888	FOR_EACH_PTR(bb->insns, insn) {
889		enum opcode op = insn->opcode;
890		if (op == OP_PHI)
891			continue;
892		INSERT_CURRENT(phi_node, insn);
893		return;
894	} END_FOR_EACH_PTR(insn);
895
896	// FIXME
897	add_instruction(&bb->insns, phi_node);
898}
899
900struct instruction *insert_phi_node(struct basic_block *bb, struct symbol *var)
901{
902	struct instruction *phi_node = alloc_phi_node(bb, var, var->ident);
903	add_phi_node(bb, phi_node);
904	return phi_node;
905}
906
907/*
908 * We carry the "access_data" structure around for any accesses,
909 * which simplifies things a lot. It contains all the access
910 * information in one place.
911 */
912struct access_data {
913	struct symbol *type;		// ctype
914	struct symbol *btype;		// base type of bitfields
915	pseudo_t address;		// pseudo containing address ..
916	unsigned int offset;		// byte offset
917};
918
919static int linearize_simple_address(struct entrypoint *ep,
920	struct expression *addr,
921	struct access_data *ad)
922{
923	if (addr->type == EXPR_SYMBOL) {
924		linearize_one_symbol(ep, addr->symbol);
925		ad->address = symbol_pseudo(ep, addr->symbol);
926		return 1;
927	}
928	if (addr->type == EXPR_BINOP) {
929		if (addr->right->type == EXPR_VALUE) {
930			if (addr->op == '+') {
931				ad->offset += get_expression_value(addr->right);
932				return linearize_simple_address(ep, addr->left, ad);
933			}
934		}
935	}
936	ad->address = linearize_expression(ep, addr);
937	return 1;
938}
939
940static struct symbol *bitfield_base_type(struct symbol *sym)
941{
942	struct symbol *base = sym;
943
944	if (sym) {
945		if (sym->type == SYM_NODE)
946			base = base->ctype.base_type;
947		if (base->type == SYM_BITFIELD)
948			return base->ctype.base_type;
949	}
950	return sym;
951}
952
953static int linearize_address_gen(struct entrypoint *ep,
954	struct expression *expr,
955	struct access_data *ad)
956{
957	struct symbol *ctype = expr->ctype;
958
959	if (!ctype)
960		return 0;
961	ad->type = ctype;
962	if (expr->type == EXPR_PREOP && expr->op == '*')
963		return linearize_simple_address(ep, expr->unop, ad);
964
965	warning(expr->pos, "generating address of non-lvalue (%d)", expr->type);
966	return 0;
967}
968
969static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
970{
971	struct instruction *insn;
972	pseudo_t new;
973
974	if (!ep->active)
975		return VOID;
976
977	insn = alloc_typed_instruction(OP_LOAD, ad->btype);
978	new = alloc_pseudo(insn);
979
980	insn->target = new;
981	insn->offset = ad->offset;
982	insn->is_volatile = ad->type && (ad->type->ctype.modifiers & MOD_VOLATILE);
983	use_pseudo(insn, ad->address, &insn->src);
984	add_one_insn(ep, insn);
985	return new;
986}
987
988static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t value)
989{
990	struct basic_block *bb = ep->active;
991	struct instruction *store;
992
993	if (!bb)
994		return;
995
996	store = alloc_typed_instruction(OP_STORE, ad->btype);
997	store->offset = ad->offset;
998	store->is_volatile = ad->type && (ad->type->ctype.modifiers & MOD_VOLATILE);
999	use_pseudo(store, value, &store->target);
1000	use_pseudo(store, ad->address, &store->src);
1001	add_one_insn(ep, store);
1002}
1003
1004static pseudo_t linearize_bitfield_insert(struct entrypoint *ep,
1005	pseudo_t ori, pseudo_t val, struct symbol *ctype, struct symbol *btype)
1006{
1007	unsigned int shift = ctype->bit_offset;
1008	unsigned int size = ctype->bit_size;
1009	unsigned long long mask = ((1ULL << size) - 1);
1010	unsigned long long smask= bits_mask(btype->bit_size);
1011
1012	val = add_cast(ep, btype, ctype, OP_ZEXT, val);
1013	if (shift) {
1014		val = add_binary_op(ep, btype, OP_SHL, val, value_pseudo(shift));
1015		mask <<= shift;
1016	}
1017	ori = add_binary_op(ep, btype, OP_AND, ori, value_pseudo(~mask & smask));
1018	val = add_binary_op(ep, btype, OP_OR, ori, val);
1019
1020	return val;
1021}
1022
1023static pseudo_t linearize_store_gen(struct entrypoint *ep,
1024		pseudo_t value,
1025		struct access_data *ad)
1026{
1027	struct symbol *ctype = ad->type;
1028	struct symbol *btype;
1029	pseudo_t store = value;
1030
1031	if (!ep->active)
1032		return VOID;
1033
1034	btype = ad->btype = bitfield_base_type(ctype);
1035	if (type_size(btype) != type_size(ctype)) {
1036		pseudo_t orig = add_load(ep, ad);
1037		store = linearize_bitfield_insert(ep, orig, value, ctype, btype);
1038	}
1039	add_store(ep, ad, store);
1040	return value;
1041}
1042
1043static void taint_undefined_behaviour(struct instruction *insn)
1044{
1045	pseudo_t src2;
1046
1047	switch (insn->opcode) {
1048	case OP_LSR:
1049	case OP_ASR:
1050	case OP_SHL:
1051		src2 = insn->src2;
1052		if (src2->type != PSEUDO_VAL)
1053			break;
1054		if ((unsigned long long)src2->value >= insn->size)
1055			insn->tainted = 1;
1056		break;
1057	}
1058}
1059
1060static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right)
1061{
1062	struct instruction *insn = alloc_typed_instruction(op, ctype);
1063	pseudo_t target = alloc_pseudo(insn);
1064	insn->target = target;
1065	use_pseudo(insn, left, &insn->src1);
1066	use_pseudo(insn, right, &insn->src2);
1067	add_one_insn(ep, insn);
1068	return target;
1069}
1070
1071static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val)
1072{
1073	struct instruction *insn = alloc_typed_instruction(OP_SETVAL, ctype);
1074	pseudo_t target = alloc_pseudo(insn);
1075	insn->target = target;
1076	insn->val = val;
1077	add_one_insn(ep, insn);
1078	return target;
1079}
1080
1081static pseudo_t add_setfval(struct entrypoint *ep, struct symbol *ctype, long double fval)
1082{
1083	struct instruction *insn = alloc_typed_instruction(OP_SETFVAL, ctype);
1084	pseudo_t target = alloc_pseudo(insn);
1085	insn->target = target;
1086	insn->fvalue = fval;
1087	add_one_insn(ep, insn);
1088	return target;
1089}
1090
1091static pseudo_t add_symbol_address(struct entrypoint *ep, struct symbol *sym)
1092{
1093	struct instruction *insn = alloc_instruction(OP_SYMADDR, bits_in_pointer);
1094	pseudo_t target = alloc_pseudo(insn);
1095
1096	insn->target = target;
1097	use_pseudo(insn, symbol_pseudo(ep, sym), &insn->src);
1098	add_one_insn(ep, insn);
1099	return target;
1100}
1101
1102static pseudo_t linearize_bitfield_extract(struct entrypoint *ep,
1103		pseudo_t val, struct symbol *ctype, struct symbol *btype)
1104{
1105	unsigned int off = ctype->bit_offset;
1106
1107	if (off) {
1108		pseudo_t shift = value_pseudo(off);
1109		val = add_binary_op(ep, btype, OP_LSR, val, shift);
1110	}
1111	val = cast_pseudo(ep, val, btype, ctype);
1112	return val;
1113}
1114
1115static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad)
1116{
1117	struct symbol *ctype = ad->type;
1118	struct symbol *btype;
1119	pseudo_t new;
1120
1121	if (!ep->active)
1122		return VOID;
1123
1124	btype = ad->btype = bitfield_base_type(ctype);
1125	new = add_load(ep, ad);
1126	if (ctype->bit_size != type_size(btype))
1127		new = linearize_bitfield_extract(ep, new, ctype, btype);
1128	return new;
1129}
1130
1131static pseudo_t linearize_access(struct entrypoint *ep, struct expression *expr)
1132{
1133	struct access_data ad = { NULL, };
1134	pseudo_t value;
1135
1136	if (!linearize_address_gen(ep, expr, &ad))
1137		return VOID;
1138	value = linearize_load_gen(ep, &ad);
1139	return value;
1140}
1141
1142static pseudo_t linearize_inc_dec(struct entrypoint *ep, struct expression *expr, int postop)
1143{
1144	struct access_data ad = { NULL, };
1145	pseudo_t old, new, one;
1146	int op = expr->op == SPECIAL_INCREMENT ? OP_ADD : OP_SUB;
1147
1148	if (!linearize_address_gen(ep, expr->unop, &ad))
1149		return VOID;
1150
1151	old = linearize_load_gen(ep, &ad);
1152	op = opcode_float(op, expr->ctype);
1153	if (is_float_type(expr->ctype))
1154		one = add_setfval(ep, expr->ctype, expr->op_value);
1155	else
1156		one = value_pseudo(expr->op_value);
1157	if (ad.btype != ad.type)
1158		old = cast_pseudo(ep, old, ad.type, ad.btype);
1159	new = add_binary_op(ep, ad.btype, op, old, one);
1160	if (ad.btype != ad.type)
1161		new = cast_pseudo(ep, new, ad.btype, ad.type);
1162	linearize_store_gen(ep, new, &ad);
1163	return postop ? old : new;
1164}
1165
1166static pseudo_t add_unop(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t src)
1167{
1168	struct instruction *insn = alloc_typed_instruction(op, ctype);
1169	pseudo_t new = alloc_pseudo(insn);
1170
1171	insn->target = new;
1172	use_pseudo(insn, src, &insn->src1);
1173	add_one_insn(ep, insn);
1174	return new;
1175}
1176
1177static pseudo_t add_cast(struct entrypoint *ep, struct symbol *to,
1178			 struct symbol *from, int op, pseudo_t src)
1179{
1180	pseudo_t new = add_unop(ep, to, op, src);
1181	new->def->orig_type = from;
1182	return new;
1183}
1184
1185static pseudo_t linearize_slice(struct entrypoint *ep, struct expression *expr)
1186{
1187	pseudo_t pre = linearize_expression(ep, expr->base);
1188	struct instruction *insn = alloc_typed_instruction(OP_SLICE, expr->ctype);
1189	pseudo_t new = alloc_pseudo(insn);
1190
1191	insn->target = new;
1192	insn->from = expr->r_bitpos;
1193	insn->len = expr->r_nrbits;
1194	use_pseudo(insn, pre, &insn->base);
1195	add_one_insn(ep, insn);
1196	return new;
1197}
1198
1199static pseudo_t linearize_regular_preop(struct entrypoint *ep, struct expression *expr)
1200{
1201	pseudo_t pre = linearize_expression(ep, expr->unop);
1202	struct symbol *ctype = expr->ctype;
1203	switch (expr->op) {
1204	case '+':
1205		return pre;
1206	case '!': {
1207		pseudo_t zero = value_pseudo(0);
1208		return add_binary_op(ep, ctype, OP_SET_EQ, pre, zero);
1209	}
1210	case '~':
1211		return add_unop(ep, ctype, OP_NOT, pre);
1212	case '-':
1213		return add_unop(ep, ctype, opcode_float(OP_NEG, ctype), pre);
1214	}
1215	return VOID;
1216}
1217
1218static pseudo_t linearize_preop(struct entrypoint *ep, struct expression *expr)
1219{
1220	/*
1221	 * '*' is an lvalue access, and is fundamentally different
1222	 * from an arithmetic operation. Maybe it should have an
1223	 * expression type of its own..
1224	 */
1225	if (expr->op == '*')
1226		return linearize_access(ep, expr);
1227	if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT)
1228		return linearize_inc_dec(ep, expr, 0);
1229	return linearize_regular_preop(ep, expr);
1230}
1231
1232static pseudo_t linearize_postop(struct entrypoint *ep, struct expression *expr)
1233{
1234	return linearize_inc_dec(ep, expr, 1);
1235}
1236
1237/*
1238 * Casts to pointers are "less safe" than other casts, since
1239 * they imply type-unsafe accesses. "void *" is a special
1240 * case, since you can't access through it anyway without another
1241 * cast.
1242 */
1243enum mtype {
1244	MTYPE_UINT,
1245	MTYPE_SINT,
1246	MTYPE_PTR,
1247	MTYPE_VPTR,	// TODO: must be removed ?
1248	MTYPE_FLOAT,
1249	MTYPE_BAD,
1250};
1251
1252static enum mtype get_mtype(struct symbol *s)
1253{
1254	int sign = (s->ctype.modifiers & MOD_SIGNED) ? 1 : 0;
1255
1256retry:	switch (s->type) {
1257	case SYM_NODE:
1258		s = s->ctype.base_type;
1259		goto retry;
1260	case SYM_PTR:
1261		if (s->ctype.base_type == &void_ctype)
1262			return MTYPE_VPTR;
1263		return MTYPE_PTR;
1264	case SYM_BITFIELD:
1265	case SYM_RESTRICT:
1266	case SYM_FOULED:
1267	case SYM_ENUM:
1268		s = s->ctype.base_type;
1269		/* fall-through */
1270	case_int:
1271		return sign ? MTYPE_SINT : MTYPE_UINT;
1272	case SYM_BASETYPE:
1273		if (s->ctype.base_type == &fp_type)
1274			return MTYPE_FLOAT;
1275		if (s->ctype.base_type == &int_type)
1276			goto case_int;
1277		/* fall-through */
1278	default:
1279		return MTYPE_BAD;
1280	}
1281}
1282
1283static int get_cast_opcode(struct symbol *dst, struct symbol *src)
1284{
1285	enum mtype stype = get_mtype(src);
1286	enum mtype dtype = get_mtype(dst);
1287
1288	switch (dtype) {
1289	case MTYPE_FLOAT:
1290		switch (stype) {
1291		case MTYPE_FLOAT:
1292			if (dst->bit_size == src->bit_size)
1293				return OP_NOP;
1294			return OP_FCVTF;
1295		case MTYPE_UINT:
1296			return OP_UCVTF;
1297		case MTYPE_SINT:
1298			return OP_SCVTF;
1299		default:
1300			return OP_BADOP;
1301		}
1302	case MTYPE_PTR:
1303		switch (stype) {
1304		case MTYPE_UINT:
1305		case MTYPE_SINT:
1306			return OP_UTPTR;
1307		case MTYPE_PTR:
1308		case MTYPE_VPTR:
1309			return OP_PTRCAST;
1310		default:
1311			return OP_BADOP;
1312		}
1313	case MTYPE_VPTR:
1314		switch (stype) {
1315		case MTYPE_PTR:
1316		case MTYPE_VPTR:
1317		case MTYPE_UINT:
1318			stype = MTYPE_UINT;
1319			/* fall through */
1320		case MTYPE_SINT:
1321			break;
1322		default:
1323			return OP_BADOP;
1324		}
1325		/* fall through */
1326	case MTYPE_UINT:
1327	case MTYPE_SINT:
1328		switch (stype) {
1329		case MTYPE_FLOAT:
1330			return dtype == MTYPE_UINT ? OP_FCVTU : OP_FCVTS;
1331		case MTYPE_PTR:
1332			return OP_PTRTU;
1333		case MTYPE_VPTR:
1334		case MTYPE_UINT:
1335		case MTYPE_SINT:
1336			if (dst->bit_size ==src->bit_size)
1337				return OP_NOP;
1338			if (dst->bit_size  < src->bit_size)
1339				return OP_TRUNC;
1340			return stype == MTYPE_SINT ? OP_SEXT : OP_ZEXT;
1341		default:
1342			return OP_BADOP;
1343		}
1344		/* fall through */
1345	default:
1346		if (src->type == SYM_NODE)
1347			src = src->ctype.base_type;
1348		if (dst->type == SYM_NODE)
1349			dst = dst->ctype.base_type;
1350		if (src == dst)
1351			return OP_NOP;
1352		return OP_BADOP;
1353	}
1354}
1355
1356static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *from, struct symbol *to)
1357{
1358	const struct position pos = current_pos;
1359	pseudo_t result;
1360	struct instruction *insn;
1361	int opcode;
1362
1363	if (src == VOID)
1364		return VOID;
1365	if (!from || !to)
1366		return VOID;
1367	if (from->bit_size < 0 || to->bit_size < 0)
1368		return VOID;
1369	opcode = get_cast_opcode(to, from);
1370	switch (opcode) {
1371	case OP_NOP:
1372		return src;
1373	case OP_UTPTR:
1374		if (from->bit_size == to->bit_size)
1375			break;
1376		if (src == value_pseudo(0))
1377			break;
1378		if (Wint_to_pointer_cast)
1379			warning(pos, "non size-preserving integer to pointer cast");
1380		src = cast_pseudo(ep, src, from, size_t_ctype);
1381		from = size_t_ctype;
1382		break;
1383	case OP_PTRTU:
1384		if (from->bit_size == to->bit_size)
1385			break;
1386		if (Wpointer_to_int_cast)
1387			warning(pos, "non size-preserving pointer to integer cast");
1388		src = cast_pseudo(ep, src, from, size_t_ctype);
1389		return cast_pseudo(ep, src, size_t_ctype, to);
1390	case OP_BADOP:
1391		return VOID;
1392	default:
1393		break;
1394	}
1395	insn = alloc_typed_instruction(opcode, to);
1396	result = alloc_pseudo(insn);
1397	insn->target = result;
1398	insn->orig_type = from;
1399	use_pseudo(insn, src, &insn->src);
1400	add_one_insn(ep, insn);
1401	return result;
1402}
1403
1404static int map_opcode(int opcode, struct symbol *ctype)
1405{
1406	if (ctype && is_float_type(ctype))
1407		return opcode_table[opcode].to_float;
1408	if (ctype && (ctype->ctype.modifiers & MOD_SIGNED)) {
1409		switch(opcode) {
1410		case OP_DIVU: case OP_MODU: case OP_LSR:
1411			opcode++;
1412		}
1413	}
1414	return opcode;
1415}
1416
1417static inline pseudo_t add_convert_to_bool(struct entrypoint *ep, pseudo_t src, struct symbol *type)
1418{
1419	pseudo_t zero;
1420	int op;
1421
1422	if (!type || src == VOID)
1423		return VOID;
1424	if (is_bool_type(type))
1425		return src;
1426	if (src->type == PSEUDO_VAL && (src->value == 0 || src->value == 1))
1427		return src;
1428	if (is_float_type(type)) {
1429		zero = add_setfval(ep, type, 0.0);
1430		op = map_opcode(OP_SET_NE, type);
1431	} else {
1432		zero = value_pseudo(0);
1433		op = OP_SET_NE;
1434	}
1435	return add_binary_op(ep, &bool_ctype, op, src, zero);
1436}
1437
1438static pseudo_t linearize_expression_to_bool(struct entrypoint *ep, struct expression *expr)
1439{
1440	pseudo_t dst;
1441	dst = linearize_expression(ep, expr);
1442	dst = add_convert_to_bool(ep, dst, expr->ctype);
1443	return dst;
1444}
1445
1446static pseudo_t linearize_assignment(struct entrypoint *ep, struct expression *expr)
1447{
1448	struct access_data ad = { NULL, };
1449	struct expression *target = expr->left;
1450	struct expression *src = expr->right;
1451	struct symbol *ctype;
1452	pseudo_t value;
1453
1454	value = linearize_expression(ep, src);
1455	if (!target || !linearize_address_gen(ep, target, &ad))
1456		return value;
1457	if (expr->op != '=') {
1458		pseudo_t oldvalue = linearize_load_gen(ep, &ad);
1459		pseudo_t dst;
1460		static const int op_trans[] = {
1461			[SPECIAL_ADD_ASSIGN - SPECIAL_BASE] = OP_ADD,
1462			[SPECIAL_SUB_ASSIGN - SPECIAL_BASE] = OP_SUB,
1463			[SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = OP_MUL,
1464			[SPECIAL_DIV_ASSIGN - SPECIAL_BASE] = OP_DIVU,
1465			[SPECIAL_MOD_ASSIGN - SPECIAL_BASE] = OP_MODU,
1466			[SPECIAL_SHL_ASSIGN - SPECIAL_BASE] = OP_SHL,
1467			[SPECIAL_SHR_ASSIGN - SPECIAL_BASE] = OP_LSR,
1468			[SPECIAL_AND_ASSIGN - SPECIAL_BASE] = OP_AND,
1469			[SPECIAL_OR_ASSIGN  - SPECIAL_BASE] = OP_OR,
1470			[SPECIAL_XOR_ASSIGN - SPECIAL_BASE] = OP_XOR
1471		};
1472		int opcode;
1473
1474		if (!src)
1475			return VOID;
1476
1477		ctype = src->ctype;
1478		oldvalue = cast_pseudo(ep, oldvalue, target->ctype, ctype);
1479		opcode = map_opcode(op_trans[expr->op - SPECIAL_BASE], ctype);
1480		dst = add_binary_op(ep, ctype, opcode, oldvalue, value);
1481		taint_undefined_behaviour(dst->def);
1482		value = cast_pseudo(ep, dst, ctype, expr->ctype);
1483	}
1484	value = linearize_store_gen(ep, value, &ad);
1485	return value;
1486}
1487
1488static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expression *expr)
1489{
1490	struct expression *arg, *fn;
1491	struct instruction *insn = alloc_typed_instruction(OP_CALL, expr->ctype);
1492	pseudo_t retval, call;
1493	struct ctype *ctype = NULL;
1494	struct symbol *fntype;
1495	struct context *context;
1496
1497	if (!expr->ctype)
1498		return VOID;
1499
1500	fn = expr->fn;
1501	fntype = fn->ctype;
1502	ctype = &fntype->ctype;
1503	if (fntype->type == SYM_NODE)
1504		fntype = fntype->ctype.base_type;
1505
1506	add_symbol(&insn->fntypes, fntype);
1507	FOR_EACH_PTR(expr->args, arg) {
1508		pseudo_t new = linearize_expression(ep, arg);
1509		use_pseudo(insn, new, add_pseudo(&insn->arguments, new));
1510		add_symbol(&insn->fntypes, arg->ctype);
1511	} END_FOR_EACH_PTR(arg);
1512
1513	if (fn->type == EXPR_PREOP && fn->op == '*' && is_func_type(fn->ctype))
1514		fn = fn->unop;
1515
1516	if (fn->type == EXPR_SYMBOL) {
1517		call = symbol_pseudo(ep, fn->symbol);
1518	} else {
1519		call = linearize_expression(ep, fn);
1520	}
1521	use_pseudo(insn, call, &insn->func);
1522	retval = VOID;
1523	if (expr->ctype != &void_ctype)
1524		retval = alloc_pseudo(insn);
1525	insn->target = retval;
1526	add_one_insn(ep, insn);
1527
1528	if (ctype) {
1529		FOR_EACH_PTR(ctype->contexts, context) {
1530			int in = context->in;
1531			int out = context->out;
1532			int check = 0;
1533			int context_diff;
1534			if (in < 0) {
1535				check = 1;
1536				in = 0;
1537			}
1538			if (out < 0) {
1539				check = 0;
1540				out = 0;
1541			}
1542			context_diff = out - in;
1543			if (check || context_diff) {
1544				insn = alloc_instruction(OP_CONTEXT, 0);
1545				insn->increment = context_diff;
1546				insn->check = check;
1547				insn->context_expr = context->context;
1548				add_one_insn(ep, insn);
1549			}
1550		} END_FOR_EACH_PTR(context);
1551	}
1552
1553	return retval;
1554}
1555
1556static pseudo_t linearize_binop_bool(struct entrypoint *ep, struct expression *expr)
1557{
1558	pseudo_t src1, src2, dst;
1559	int op = (expr->op == SPECIAL_LOGICAL_OR) ? OP_OR : OP_AND;
1560
1561	src1 = linearize_expression_to_bool(ep, expr->left);
1562	src2 = linearize_expression_to_bool(ep, expr->right);
1563	dst = add_binary_op(ep, &bool_ctype, op, src1, src2);
1564	if (expr->ctype != &bool_ctype)
1565		dst = cast_pseudo(ep, dst, &bool_ctype, expr->ctype);
1566	return dst;
1567}
1568
1569static pseudo_t linearize_binop(struct entrypoint *ep, struct expression *expr)
1570{
1571	pseudo_t src1, src2, dst;
1572	static const int opcode[] = {
1573		['+'] = OP_ADD, ['-'] = OP_SUB,
1574		['*'] = OP_MUL, ['/'] = OP_DIVU,
1575		['%'] = OP_MODU, ['&'] = OP_AND,
1576		['|'] = OP_OR,  ['^'] = OP_XOR,
1577		[SPECIAL_LEFTSHIFT] = OP_SHL,
1578		[SPECIAL_RIGHTSHIFT] = OP_LSR,
1579	};
1580	int op;
1581
1582	src1 = linearize_expression(ep, expr->left);
1583	src2 = linearize_expression(ep, expr->right);
1584	op = map_opcode(opcode[expr->op], expr->ctype);
1585	dst = add_binary_op(ep, expr->ctype, op, src1, src2);
1586	taint_undefined_behaviour(dst->def);
1587	return dst;
1588}
1589
1590static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
1591
1592static pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
1593
1594static pseudo_t linearize_select(struct entrypoint *ep, struct expression *expr)
1595{
1596	pseudo_t cond, valt, valf, res;
1597	struct instruction *insn;
1598
1599	valt = linearize_expression(ep, expr->cond_true);
1600	valf = linearize_expression(ep, expr->cond_false);
1601	cond = linearize_expression(ep, expr->conditional);
1602
1603	insn = alloc_typed_instruction(OP_SEL, expr->ctype);
1604	if (!expr->cond_true)
1605		valt = cond;
1606	use_pseudo(insn, cond, &insn->src1);
1607	use_pseudo(insn, valt, &insn->src2);
1608	use_pseudo(insn, valf, &insn->src3);
1609
1610	res = alloc_pseudo(insn);
1611	insn->target = res;
1612	add_one_insn(ep, insn);
1613	return res;
1614}
1615
1616static pseudo_t add_join_conditional(struct entrypoint *ep, struct expression *expr,
1617				     pseudo_t phi1, pseudo_t phi2)
1618{
1619	pseudo_t target;
1620	struct instruction *phi_node;
1621
1622	if (phi1 == VOID)
1623		return phi2;
1624	if (phi2 == VOID)
1625		return phi1;
1626
1627	phi_node = alloc_typed_instruction(OP_PHI, expr->ctype);
1628	use_pseudo(phi_node, phi1, add_pseudo(&phi_node->phi_list, phi1));
1629	use_pseudo(phi_node, phi2, add_pseudo(&phi_node->phi_list, phi2));
1630	phi_node->target = target = alloc_pseudo(phi_node);
1631	add_one_insn(ep, phi_node);
1632	return target;
1633}
1634
1635static pseudo_t linearize_short_conditional(struct entrypoint *ep, struct expression *expr,
1636					    struct expression *cond,
1637					    struct expression *expr_false)
1638{
1639	pseudo_t src1, src2;
1640	struct basic_block *bb_false;
1641	struct basic_block *merge;
1642	pseudo_t phi1, phi2;
1643
1644	if (!expr_false || !ep->active)
1645		return VOID;
1646
1647	bb_false = alloc_basic_block(ep, expr_false->pos);
1648	merge = alloc_basic_block(ep, expr->pos);
1649
1650	src1 = linearize_expression(ep, cond);
1651	phi1 = alloc_phi(ep->active, src1, expr->ctype);
1652	add_branch(ep, src1, merge, bb_false);
1653
1654	set_activeblock(ep, bb_false);
1655	src2 = linearize_expression(ep, expr_false);
1656	phi2 = alloc_phi(ep->active, src2, expr->ctype);
1657	set_activeblock(ep, merge);
1658
1659	return add_join_conditional(ep, expr, phi1, phi2);
1660}
1661
1662static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *expr,
1663				      struct expression *cond,
1664				      struct expression *expr_true,
1665				      struct expression *expr_false)
1666{
1667	pseudo_t src1, src2;
1668	pseudo_t phi1, phi2;
1669	struct basic_block *bb_true, *bb_false, *merge;
1670
1671	if (!cond || !expr_true || !expr_false || !ep->active)
1672		return VOID;
1673	bb_true = alloc_basic_block(ep, expr_true->pos);
1674	bb_false = alloc_basic_block(ep, expr_false->pos);
1675	merge = alloc_basic_block(ep, expr->pos);
1676
1677	linearize_cond_branch(ep, cond, bb_true, bb_false);
1678
1679	set_activeblock(ep, bb_true);
1680	src1 = linearize_expression(ep, expr_true);
1681	phi1 = alloc_phi(ep->active, src1, expr->ctype);
1682	add_goto(ep, merge);
1683
1684	set_activeblock(ep, bb_false);
1685	src2 = linearize_expression(ep, expr_false);
1686	phi2 = alloc_phi(ep->active, src2, expr->ctype);
1687	set_activeblock(ep, merge);
1688
1689	return add_join_conditional(ep, expr, phi1, phi2);
1690}
1691
1692static void insert_phis(struct basic_block *bb, pseudo_t src, struct symbol *ctype,
1693	struct instruction *node)
1694{
1695	struct basic_block *parent;
1696
1697	FOR_EACH_PTR(bb->parents, parent) {
1698		struct instruction *br = delete_last_instruction(&parent->insns);
1699		pseudo_t phi = alloc_phi(parent, src, ctype);
1700		add_instruction(&parent->insns, br);
1701		use_pseudo(node, phi, add_pseudo(&node->phi_list, phi));
1702	} END_FOR_EACH_PTR(parent);
1703}
1704
1705static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr)
1706{
1707	struct symbol *ctype = expr->ctype;
1708	struct basic_block *other, *merge;
1709	struct instruction *node;
1710	pseudo_t src1, src2, phi2;
1711
1712	if (!ep->active || !expr->left || !expr->right)
1713		return VOID;
1714
1715	other = alloc_basic_block(ep, expr->right->pos);
1716	merge = alloc_basic_block(ep, expr->pos);
1717	node = alloc_phi_node(merge, ctype, NULL);
1718
1719	// LHS and its shortcut
1720	if (expr->op == SPECIAL_LOGICAL_OR) {
1721		linearize_cond_branch(ep, expr->left, merge, other);
1722		src1 = value_pseudo(1);
1723	} else {
1724		linearize_cond_branch(ep, expr->left, other, merge);
1725		src1 = value_pseudo(0);
1726	}
1727	insert_phis(merge, src1, ctype, node);
1728
1729	// RHS
1730	set_activeblock(ep, other);
1731	src2 = linearize_expression_to_bool(ep, expr->right);
1732	src2 = cast_pseudo(ep, src2, &bool_ctype, ctype);
1733	phi2 = alloc_phi(ep->active, src2, ctype);
1734	use_pseudo(node, phi2, add_pseudo(&node->phi_list, phi2));
1735
1736	// join
1737	set_activeblock(ep, merge);
1738	add_instruction(&merge->insns, node);
1739	return node->target;
1740}
1741
1742static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr)
1743{
1744	static const int cmpop[] = {
1745		['>'] = OP_SET_GT, ['<'] = OP_SET_LT,
1746		[SPECIAL_EQUAL] = OP_SET_EQ,
1747		[SPECIAL_NOTEQUAL] = OP_SET_NE,
1748		[SPECIAL_GTE] = OP_SET_GE,
1749		[SPECIAL_LTE] = OP_SET_LE,
1750		[SPECIAL_UNSIGNED_LT] = OP_SET_B,
1751		[SPECIAL_UNSIGNED_GT] = OP_SET_A,
1752		[SPECIAL_UNSIGNED_LTE] = OP_SET_BE,
1753		[SPECIAL_UNSIGNED_GTE] = OP_SET_AE,
1754	};
1755	int op = opcode_float(cmpop[expr->op], expr->right->ctype);
1756	pseudo_t src1 = linearize_expression(ep, expr->left);
1757	pseudo_t src2 = linearize_expression(ep, expr->right);
1758	pseudo_t dst = add_binary_op(ep, expr->ctype, op, src1, src2);
1759	return dst;
1760}
1761
1762
1763static pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1764{
1765	pseudo_t cond;
1766
1767	if (!expr || !bb_reachable(ep->active))
1768		return VOID;
1769
1770	switch (expr->type) {
1771
1772	case EXPR_STRING:
1773	case EXPR_VALUE:
1774		add_goto(ep, expr->value ? bb_true : bb_false);
1775		return VOID;
1776
1777	case EXPR_FVALUE:
1778		add_goto(ep, expr->fvalue ? bb_true : bb_false);
1779		return VOID;
1780
1781	case EXPR_LOGICAL:
1782		linearize_logical_branch(ep, expr, bb_true, bb_false);
1783		return VOID;
1784
1785	case EXPR_COMPARE:
1786		cond = linearize_compare(ep, expr);
1787		add_branch(ep, cond, bb_true, bb_false);
1788		break;
1789
1790	case EXPR_PREOP:
1791		if (expr->op == '!')
1792			return linearize_cond_branch(ep, expr->unop, bb_false, bb_true);
1793		/* fall through */
1794	default: {
1795		cond = linearize_expression_to_bool(ep, expr);
1796		add_branch(ep, cond, bb_true, bb_false);
1797
1798		return VOID;
1799	}
1800	}
1801	return VOID;
1802}
1803
1804
1805
1806static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1807{
1808	struct basic_block *next = alloc_basic_block(ep, expr->pos);
1809
1810	if (expr->op == SPECIAL_LOGICAL_OR)
1811		linearize_cond_branch(ep, expr->left, bb_true, next);
1812	else
1813		linearize_cond_branch(ep, expr->left, next, bb_false);
1814	set_activeblock(ep, next);
1815	linearize_cond_branch(ep, expr->right, bb_true, bb_false);
1816	return VOID;
1817}
1818
1819static pseudo_t linearize_cast(struct entrypoint *ep, struct expression *expr)
1820{
1821	pseudo_t src;
1822	struct expression *orig = expr->cast_expression;
1823
1824	if (!orig)
1825		return VOID;
1826
1827	src = linearize_expression(ep, orig);
1828	return cast_pseudo(ep, src, orig->ctype, expr->ctype);
1829}
1830
1831static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *ad)
1832{
1833	switch (initializer->type) {
1834	case EXPR_INITIALIZER: {
1835		struct expression *expr;
1836		FOR_EACH_PTR(initializer->expr_list, expr) {
1837			linearize_initializer(ep, expr, ad);
1838		} END_FOR_EACH_PTR(expr);
1839		break;
1840	}
1841	case EXPR_POS:
1842		ad->offset = initializer->init_offset;
1843		linearize_initializer(ep, initializer->init_expr, ad);
1844		break;
1845	default: {
1846		pseudo_t value = linearize_expression(ep, initializer);
1847		ad->type = initializer->ctype;
1848		linearize_store_gen(ep, value, ad);
1849		return value;
1850	}
1851	}
1852
1853	return VOID;
1854}
1855
1856static void linearize_argument(struct entrypoint *ep, struct symbol *arg, int nr)
1857{
1858	struct access_data ad = { NULL, };
1859
1860	ad.type = arg;
1861	ad.address = symbol_pseudo(ep, arg);
1862	linearize_store_gen(ep, argument_pseudo(ep, nr), &ad);
1863}
1864
1865static pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr)
1866{
1867	if (!expr)
1868		return VOID;
1869
1870	current_pos = expr->pos;
1871	switch (expr->type) {
1872	case EXPR_SYMBOL:
1873		linearize_one_symbol(ep, expr->symbol);
1874		return add_symbol_address(ep, expr->symbol);
1875
1876	case EXPR_VALUE:
1877		return value_pseudo(expr->value);
1878
1879	case EXPR_STRING:
1880	case EXPR_LABEL:
1881		return add_setval(ep, expr->ctype, expr);
1882
1883	case EXPR_FVALUE:
1884		return add_setfval(ep, expr->ctype, expr->fvalue);
1885
1886	case EXPR_STATEMENT:
1887		return linearize_statement(ep, expr->statement);
1888
1889	case EXPR_CALL:
1890		return linearize_call_expression(ep, expr);
1891
1892	case EXPR_BINOP:
1893		if (expr->op == SPECIAL_LOGICAL_AND || expr->op == SPECIAL_LOGICAL_OR)
1894			return linearize_binop_bool(ep, expr);
1895		return linearize_binop(ep, expr);
1896
1897	case EXPR_LOGICAL:
1898		return linearize_logical(ep, expr);
1899
1900	case EXPR_COMPARE:
1901		return  linearize_compare(ep, expr);
1902
1903	case EXPR_SELECT:
1904		return	linearize_select(ep, expr);
1905
1906	case EXPR_CONDITIONAL:
1907		if (!expr->cond_true)
1908			return linearize_short_conditional(ep, expr, expr->conditional, expr->cond_false);
1909
1910		return  linearize_conditional(ep, expr, expr->conditional,
1911					      expr->cond_true, expr->cond_false);
1912
1913	case EXPR_COMMA:
1914		linearize_expression(ep, expr->left);
1915		return linearize_expression(ep, expr->right);
1916
1917	case EXPR_ASSIGNMENT:
1918		return linearize_assignment(ep, expr);
1919
1920	case EXPR_PREOP:
1921		return linearize_preop(ep, expr);
1922
1923	case EXPR_POSTOP:
1924		return linearize_postop(ep, expr);
1925
1926	case EXPR_CAST:
1927	case EXPR_FORCE_CAST:
1928	case EXPR_IMPLIED_CAST:
1929		return linearize_cast(ep, expr);
1930
1931	case EXPR_SLICE:
1932		return linearize_slice(ep, expr);
1933
1934	case EXPR_INITIALIZER:
1935	case EXPR_POS:
1936		warning(expr->pos, "unexpected initializer expression (%d %d)", expr->type, expr->op);
1937		return VOID;
1938	default:
1939		warning(expr->pos, "unknown expression (%d %d)", expr->type, expr->op);
1940		return VOID;
1941	}
1942	return VOID;
1943}
1944
1945static pseudo_t linearize_one_symbol(struct entrypoint *ep, struct symbol *sym)
1946{
1947	struct access_data ad = { NULL, };
1948	pseudo_t value;
1949
1950	if (!sym || !sym->initializer || sym->initialized)
1951		return VOID;
1952
1953	/* We need to output these puppies some day too.. */
1954	if (sym->ctype.modifiers & (MOD_STATIC | MOD_TOPLEVEL))
1955		return VOID;
1956
1957	sym->initialized = 1;
1958	ad.address = symbol_pseudo(ep, sym);
1959
1960	if (sym->initializer && !is_scalar_type(sym)) {
1961		// default zero initialization [6.7.9.21]
1962		// FIXME: this init the whole aggregate while
1963		// only the existing fields need to be initialized.
1964		// FIXME: this init the whole aggregate even if
1965		// all fields arelater  explicitely initialized.
1966		ad.type = sym;
1967		ad.address = symbol_pseudo(ep, sym);
1968		linearize_store_gen(ep, value_pseudo(0), &ad);
1969	}
1970
1971	value = linearize_initializer(ep, sym->initializer, &ad);
1972	return value;
1973}
1974
1975static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct statement *stmt)
1976{
1977	pseudo_t pseudo;
1978	struct statement *s;
1979
1980	pseudo = VOID;
1981	FOR_EACH_PTR(stmt->stmts, s) {
1982		pseudo = linearize_statement(ep, s);
1983	} END_FOR_EACH_PTR(s);
1984
1985	return pseudo;
1986}
1987
1988static void add_return(struct entrypoint *ep, struct basic_block *bb, struct symbol *ctype, pseudo_t src)
1989{
1990	struct instruction *phi_node = first_instruction(bb->insns);
1991	pseudo_t phi;
1992	if (!phi_node) {
1993		phi_node = alloc_typed_instruction(OP_PHI, ctype);
1994		phi_node->target = alloc_pseudo(phi_node);
1995		phi_node->bb = bb;
1996		add_instruction(&bb->insns, phi_node);
1997	}
1998	phi = alloc_phi(ep->active, src, ctype);
1999	phi->ident = &return_ident;
2000	use_pseudo(phi_node, phi, add_pseudo(&phi_node->phi_list, phi));
2001}
2002
2003static pseudo_t linearize_fn_statement(struct entrypoint *ep, struct statement *stmt)
2004{
2005	struct instruction *phi_node;
2006	struct basic_block *bb;
2007	pseudo_t pseudo;
2008
2009	pseudo = linearize_compound_statement(ep, stmt);
2010	if (!is_void_type(stmt->ret)) {			// non-void function
2011		struct basic_block *active = ep->active;
2012		if (active && !bb_terminated(active)) {	// missing return
2013			struct basic_block *bb_ret;
2014			bb_ret = get_bound_block(ep, stmt->ret);
2015			add_return(ep, bb_ret, stmt->ret, undef_pseudo());
2016		}
2017	}
2018	bb = add_label(ep, stmt->ret);
2019	phi_node = first_instruction(bb->insns);
2020	if (phi_node)
2021		pseudo = phi_node->target;
2022	return pseudo;
2023}
2024
2025static pseudo_t linearize_inlined_call(struct entrypoint *ep, struct statement *stmt)
2026{
2027	struct instruction *insn = alloc_instruction(OP_INLINED_CALL, 0);
2028	struct statement *args = stmt->args;
2029	struct basic_block *bb;
2030	pseudo_t pseudo;
2031
2032	if (args) {
2033		struct symbol *sym;
2034
2035		concat_symbol_list(args->declaration, &ep->syms);
2036		FOR_EACH_PTR(args->declaration, sym) {
2037			pseudo_t value = linearize_one_symbol(ep, sym);
2038			add_pseudo(&insn->arguments, value);
2039		} END_FOR_EACH_PTR(sym);
2040	}
2041
2042	pseudo = linearize_fn_statement(ep, stmt);
2043	insn->target = pseudo;
2044
2045	use_pseudo(insn, symbol_pseudo(ep, stmt->inline_fn), &insn->func);
2046	bb = ep->active;
2047	if (!bb->insns)
2048		bb->pos = stmt->pos;
2049	add_one_insn(ep, insn);
2050	return pseudo;
2051}
2052
2053static pseudo_t linearize_context(struct entrypoint *ep, struct statement *stmt)
2054{
2055	struct instruction *insn = alloc_instruction(OP_CONTEXT, 0);
2056	struct expression *expr = stmt->expression;
2057
2058	insn->increment = get_expression_value(expr);
2059	insn->context_expr = stmt->context;
2060	add_one_insn(ep, insn);
2061	return VOID;
2062}
2063
2064static pseudo_t linearize_range(struct entrypoint *ep, struct statement *stmt)
2065{
2066	struct instruction *insn = alloc_instruction(OP_RANGE, 0);
2067
2068	use_pseudo(insn, linearize_expression(ep, stmt->range_expression), &insn->src1);
2069	use_pseudo(insn, linearize_expression(ep, stmt->range_low), &insn->src2);
2070	use_pseudo(insn, linearize_expression(ep, stmt->range_high), &insn->src3);
2071	add_one_insn(ep, insn);
2072	return VOID;
2073}
2074
2075ALLOCATOR(asm_rules, "asm rules");
2076ALLOCATOR(asm_constraint, "asm constraints");
2077
2078static void add_asm_input(struct entrypoint *ep, struct instruction *insn, struct expression *expr,
2079	const char *constraint, const struct ident *ident)
2080{
2081	pseudo_t pseudo = linearize_expression(ep, expr);
2082	struct asm_constraint *rule = __alloc_asm_constraint(0);
2083
2084	rule->ident = ident;
2085	rule->constraint = constraint;
2086	use_pseudo(insn, pseudo, &rule->pseudo);
2087	add_ptr_list(&insn->asm_rules->inputs, rule);
2088}
2089
2090static void add_asm_output(struct entrypoint *ep, struct instruction *insn, struct expression *expr,
2091	const char *constraint, const struct ident *ident)
2092{
2093	struct access_data ad = { NULL, };
2094	pseudo_t pseudo = alloc_pseudo(insn);
2095	struct asm_constraint *rule;
2096
2097	if (!expr || !linearize_address_gen(ep, expr, &ad))
2098		return;
2099	linearize_store_gen(ep, pseudo, &ad);
2100	rule = __alloc_asm_constraint(0);
2101	rule->ident = ident;
2102	rule->constraint = constraint;
2103	use_pseudo(insn, pseudo, &rule->pseudo);
2104	add_ptr_list(&insn->asm_rules->outputs, rule);
2105}
2106
2107static pseudo_t linearize_asm_statement(struct entrypoint *ep, struct statement *stmt)
2108{
2109	struct expression *expr;
2110	struct instruction *insn;
2111	struct asm_rules *rules;
2112	const char *constraint;
2113
2114	insn = alloc_instruction(OP_ASM, 0);
2115	expr = stmt->asm_string;
2116	if (!expr || expr->type != EXPR_STRING) {
2117		warning(stmt->pos, "expected string in inline asm");
2118		return VOID;
2119	}
2120	insn->string = expr->string->data;
2121
2122	rules = __alloc_asm_rules(0);
2123	insn->asm_rules = rules;
2124
2125	/* Gather the inputs.. */
2126	FOR_EACH_PTR(stmt->asm_inputs, expr) {
2127		constraint = expr->constraint ? expr->constraint->string->data : "";
2128		add_asm_input(ep, insn, expr->expr, constraint, expr->name);
2129	} END_FOR_EACH_PTR(expr);
2130
2131	add_one_insn(ep, insn);
2132
2133	/* Assign the outputs */
2134	FOR_EACH_PTR(stmt->asm_outputs, expr) {
2135		constraint = expr->constraint ? expr->constraint->string->data : "";
2136		add_asm_output(ep, insn, expr->expr, constraint, expr->name);
2137	} END_FOR_EACH_PTR(expr);
2138
2139	return VOID;
2140}
2141
2142static int multijmp_cmp(const void *_a, const void *_b)
2143{
2144	const struct multijmp *a = _a;
2145	const struct multijmp *b = _b;
2146
2147	// "default" case?
2148	if (a->begin > a->end) {
2149		if (b->begin > b->end)
2150			return 0;
2151		return 1;
2152	}
2153	if (b->begin > b->end)
2154		return -1;
2155	if (a->begin == b->begin) {
2156		if (a->end == b->end)
2157			return 0;
2158		return (a->end < b->end) ? -1 : 1;
2159	}
2160	return a->begin < b->begin ? -1 : 1;
2161}
2162
2163static void sort_switch_cases(struct instruction *insn)
2164{
2165	sort_list((struct ptr_list **)&insn->multijmp_list, multijmp_cmp);
2166}
2167
2168static pseudo_t linearize_declaration(struct entrypoint *ep, struct statement *stmt)
2169{
2170	struct symbol *sym;
2171
2172	concat_symbol_list(stmt->declaration, &ep->syms);
2173
2174	FOR_EACH_PTR(stmt->declaration, sym) {
2175		linearize_one_symbol(ep, sym);
2176	} END_FOR_EACH_PTR(sym);
2177	return VOID;
2178}
2179
2180static pseudo_t linearize_return(struct entrypoint *ep, struct statement *stmt)
2181{
2182	struct expression *expr = stmt->expression;
2183	struct symbol *ret = stmt->ret_target;
2184	struct basic_block *bb_return = get_bound_block(ep, ret);
2185	struct basic_block *active;
2186	pseudo_t src = linearize_expression(ep, expr);
2187	active = ep->active;
2188	if (active && !is_void_type(ret)) {
2189		add_return(ep, bb_return, ret, src);
2190	}
2191	add_goto(ep, bb_return);
2192	return VOID;
2193}
2194
2195static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt)
2196{
2197	struct symbol *sym;
2198	struct instruction *switch_ins;
2199	struct basic_block *switch_end = alloc_basic_block(ep, stmt->pos);
2200	struct basic_block *active, *default_case;
2201	struct expression *expr = stmt->switch_expression;
2202	struct multijmp *jmp;
2203	pseudo_t pseudo;
2204
2205	if (!expr || !expr->ctype)
2206		return VOID;
2207	pseudo = linearize_expression(ep, expr);
2208	active = ep->active;
2209	if (!active) {
2210		active = alloc_basic_block(ep, stmt->pos);
2211		set_activeblock(ep, active);
2212	}
2213
2214	switch_ins = alloc_typed_instruction(OP_SWITCH, expr->ctype);
2215	use_pseudo(switch_ins, pseudo, &switch_ins->cond);
2216	add_one_insn(ep, switch_ins);
2217	finish_block(ep);
2218
2219	default_case = NULL;
2220	FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
2221		struct statement *case_stmt = sym->stmt;
2222		struct basic_block *bb_case = get_bound_block(ep, sym);
2223
2224		if (!case_stmt->case_expression) {
2225			default_case = bb_case;
2226			continue;
2227		} else if (case_stmt->case_expression->type != EXPR_VALUE) {
2228			continue;
2229		} else {
2230			struct expression *case_to = case_stmt->case_to;
2231			long long begin, end;
2232
2233			begin = end = case_stmt->case_expression->value;
2234			if (case_to && case_to->type == EXPR_VALUE)
2235				end = case_to->value;
2236			if (begin > end)
2237				jmp = alloc_multijmp(bb_case, end, begin);
2238			else
2239				jmp = alloc_multijmp(bb_case, begin, end);
2240
2241		}
2242		add_multijmp(&switch_ins->multijmp_list, jmp);
2243		add_bb(&bb_case->parents, active);
2244		add_bb(&active->children, bb_case);
2245	} END_FOR_EACH_PTR(sym);
2246
2247	bind_label(stmt->switch_break, switch_end, stmt->pos);
2248
2249	/* And linearize the actual statement */
2250	linearize_statement(ep, stmt->switch_statement);
2251	set_activeblock(ep, switch_end);
2252
2253	if (!default_case)
2254		default_case = switch_end;
2255
2256	jmp = alloc_multijmp(default_case, 1, 0);
2257	add_multijmp(&switch_ins->multijmp_list, jmp);
2258	add_bb(&default_case->parents, active);
2259	add_bb(&active->children, default_case);
2260	sort_switch_cases(switch_ins);
2261
2262	return VOID;
2263}
2264
2265static pseudo_t linearize_iterator(struct entrypoint *ep, struct statement *stmt)
2266{
2267	struct statement  *pre_statement = stmt->iterator_pre_statement;
2268	struct expression *pre_condition = stmt->iterator_pre_condition;
2269	struct statement  *statement = stmt->iterator_statement;
2270	struct statement  *post_statement = stmt->iterator_post_statement;
2271	struct expression *post_condition = stmt->iterator_post_condition;
2272	struct basic_block *loop_top, *loop_body, *loop_continue, *loop_end;
2273	struct symbol *sym;
2274
2275	FOR_EACH_PTR(stmt->iterator_syms, sym) {
2276		linearize_one_symbol(ep, sym);
2277	} END_FOR_EACH_PTR(sym);
2278	concat_symbol_list(stmt->iterator_syms, &ep->syms);
2279	linearize_statement(ep, pre_statement);
2280
2281	loop_body = loop_top = alloc_basic_block(ep, stmt->pos);
2282	loop_continue = alloc_basic_block(ep, stmt->pos);
2283	loop_end = alloc_basic_block(ep, stmt->pos);
2284
2285	/* An empty post-condition means that it's the same as the pre-condition */
2286	if (!post_condition) {
2287		loop_top = alloc_basic_block(ep, stmt->pos);
2288		set_activeblock(ep, loop_top);
2289	}
2290
2291	if (pre_condition)
2292			linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
2293
2294	bind_label(stmt->iterator_continue, loop_continue, stmt->pos);
2295	bind_label(stmt->iterator_break, loop_end, stmt->pos);
2296
2297	set_activeblock(ep, loop_body);
2298	linearize_statement(ep, statement);
2299	add_goto(ep, loop_continue);
2300
2301	set_activeblock(ep, loop_continue);
2302	linearize_statement(ep, post_statement);
2303	if (!post_condition)
2304		add_goto(ep, loop_top);
2305	else
2306		linearize_cond_branch(ep, post_condition, loop_top, loop_end);
2307	set_activeblock(ep, loop_end);
2308
2309	return VOID;
2310}
2311
2312static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
2313{
2314	struct basic_block *bb;
2315
2316	if (!stmt)
2317		return VOID;
2318
2319	bb = ep->active;
2320	if (bb && !bb->insns)
2321		bb->pos = stmt->pos;
2322	current_pos = stmt->pos;
2323
2324	switch (stmt->type) {
2325	case STMT_NONE:
2326		break;
2327
2328	case STMT_DECLARATION:
2329		return linearize_declaration(ep, stmt);
2330
2331	case STMT_CONTEXT:
2332		return linearize_context(ep, stmt);
2333
2334	case STMT_RANGE:
2335		return linearize_range(ep, stmt);
2336
2337	case STMT_EXPRESSION:
2338		return linearize_expression(ep, stmt->expression);
2339
2340	case STMT_ASM:
2341		return linearize_asm_statement(ep, stmt);
2342
2343	case STMT_RETURN:
2344		return linearize_return(ep, stmt);
2345
2346	case STMT_CASE: {
2347		add_label(ep, stmt->case_label);
2348		linearize_statement(ep, stmt->case_statement);
2349		break;
2350	}
2351
2352	case STMT_LABEL: {
2353		struct symbol *label = stmt->label_identifier;
2354
2355		if (label->used) {
2356			add_label(ep, label);
2357		}
2358		return linearize_statement(ep, stmt->label_statement);
2359	}
2360
2361	case STMT_GOTO: {
2362		struct symbol *sym;
2363		struct expression *expr;
2364		struct instruction *goto_ins;
2365		struct basic_block *active;
2366		pseudo_t pseudo;
2367
2368		active = ep->active;
2369		if (!bb_reachable(active))
2370			break;
2371
2372		if (stmt->goto_label) {
2373			add_goto(ep, get_bound_block(ep, stmt->goto_label));
2374			break;
2375		}
2376
2377		expr = stmt->goto_expression;
2378		if (!expr)
2379			break;
2380
2381		/* This can happen as part of simplification */
2382		if (expr->type == EXPR_LABEL) {
2383			add_goto(ep, get_bound_block(ep, expr->label_symbol));
2384			break;
2385		}
2386
2387		pseudo = linearize_expression(ep, expr);
2388		goto_ins = alloc_instruction(OP_COMPUTEDGOTO, 0);
2389		use_pseudo(goto_ins, pseudo, &goto_ins->src);
2390		add_one_insn(ep, goto_ins);
2391
2392		FOR_EACH_PTR(stmt->target_list, sym) {
2393			struct basic_block *bb_computed = get_bound_block(ep, sym);
2394			struct multijmp *jmp = alloc_multijmp(bb_computed, 1, 0);
2395			add_multijmp(&goto_ins->multijmp_list, jmp);
2396			add_bb(&bb_computed->parents, ep->active);
2397			add_bb(&active->children, bb_computed);
2398		} END_FOR_EACH_PTR(sym);
2399
2400		finish_block(ep);
2401		break;
2402	}
2403
2404	case STMT_COMPOUND:
2405		if (stmt->inline_fn)
2406			return linearize_inlined_call(ep, stmt);
2407		return linearize_compound_statement(ep, stmt);
2408
2409	/*
2410	 * This could take 'likely/unlikely' into account, and
2411	 * switch the arms around appropriately..
2412	 */
2413	case STMT_IF: {
2414		struct basic_block *bb_true, *bb_false, *endif;
2415 		struct expression *cond = stmt->if_conditional;
2416
2417		bb_true = alloc_basic_block(ep, stmt->pos);
2418		bb_false = endif = alloc_basic_block(ep, stmt->pos);
2419
2420 		linearize_cond_branch(ep, cond, bb_true, bb_false);
2421
2422		set_activeblock(ep, bb_true);
2423 		linearize_statement(ep, stmt->if_true);
2424
2425 		if (stmt->if_false) {
2426			endif = alloc_basic_block(ep, stmt->pos);
2427			add_goto(ep, endif);
2428			set_activeblock(ep, bb_false);
2429 			linearize_statement(ep, stmt->if_false);
2430		}
2431		set_activeblock(ep, endif);
2432		break;
2433	}
2434
2435	case STMT_SWITCH:
2436		return linearize_switch(ep, stmt);
2437
2438	case STMT_ITERATOR:
2439		return linearize_iterator(ep, stmt);
2440
2441	default:
2442		break;
2443	}
2444	return VOID;
2445}
2446
2447static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_type)
2448{
2449	struct statement *stmt = base_type->stmt;
2450	struct entrypoint *ep;
2451	struct basic_block *bb;
2452	struct symbol *ret_type;
2453	struct symbol *arg;
2454	struct instruction *entry;
2455	struct instruction *ret;
2456	pseudo_t result;
2457	int i;
2458
2459	if (!stmt)
2460		return NULL;
2461
2462	ep = alloc_entrypoint();
2463	ep->name = sym;
2464	sym->ep = ep;
2465	bb = alloc_basic_block(ep, sym->pos);
2466	set_activeblock(ep, bb);
2467
2468	if (stmt->type == STMT_ASM) {	// top-level asm
2469		linearize_asm_statement(ep, stmt);
2470		return ep;
2471	}
2472
2473	entry = alloc_instruction(OP_ENTRY, 0);
2474	add_one_insn(ep, entry);
2475	ep->entry = entry;
2476
2477	concat_symbol_list(base_type->arguments, &ep->syms);
2478
2479	/* FIXME!! We should do something else about varargs.. */
2480	i = 0;
2481	FOR_EACH_PTR(base_type->arguments, arg) {
2482		linearize_argument(ep, arg, ++i);
2483	} END_FOR_EACH_PTR(arg);
2484
2485	result = linearize_fn_statement(ep, stmt);
2486	ret_type = base_type->ctype.base_type;
2487	ret = alloc_typed_instruction(OP_RET, ret_type);
2488	if (type_size(ret_type) > 0)
2489		use_pseudo(ret, result, &ret->src);
2490	add_one_insn(ep, ret);
2491
2492	optimize(ep);
2493	return ep;
2494}
2495
2496struct entrypoint *linearize_symbol(struct symbol *sym)
2497{
2498	struct symbol *base_type;
2499
2500	if (!sym)
2501		return NULL;
2502	current_pos = sym->pos;
2503	base_type = sym->ctype.base_type;
2504	if (!base_type)
2505		return NULL;
2506	if (base_type->type == SYM_FN)
2507		return linearize_fn(sym, base_type);
2508	return NULL;
2509}
2510