1/*
2 * sparse/expand.c
3 *
4 * Copyright (C) 2003 Transmeta Corp.
5 *               2003-2004 Linus Torvalds
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23 * THE SOFTWARE.
24 *
25 * expand constant expressions.
26 */
27#include <stdlib.h>
28#include <stdarg.h>
29#include <stddef.h>
30#include <stdio.h>
31#include <string.h>
32#include <ctype.h>
33#include <unistd.h>
34#include <fcntl.h>
35#include <limits.h>
36
37#include "lib.h"
38#include "allocate.h"
39#include "parse.h"
40#include "token.h"
41#include "symbol.h"
42#include "target.h"
43#include "expression.h"
44#include "evaluate.h"
45#include "expand.h"
46
47
48static int expand_expression(struct expression *);
49static int expand_statement(struct statement *);
50
51// If set, don't issue a warning on divide-by-0, invalid shift, ...
52// and don't mark the expression as erroneous but leave it as-is.
53// This allows testing some characteristics of the expression
54// without creating any side-effects (e.g.: is_zero_constant()).
55static int conservative;
56
57static int expand_symbol_expression(struct expression *expr)
58{
59	struct symbol *sym = expr->symbol;
60
61	if (sym == &zero_int) {
62		if (Wundef)
63			warning(expr->pos, "undefined preprocessor identifier '%s'", show_ident(expr->symbol_name));
64		expr->type = EXPR_VALUE;
65		expr->value = 0;
66		expr->taint = 0;
67		return 0;
68	}
69
70	// expand compound literals (C99 & C11 6.5.2.5)
71	// FIXME: is this the correct way to identify them?
72	//	All compound literals are anonymous but is
73	//	the reverse true?
74	if (sym->initializer && !expr->symbol_name)
75		return expand_expression(sym->initializer);
76
77	/* The cost of a symbol expression is lower for on-stack symbols */
78	return (sym->ctype.modifiers & (MOD_STATIC | MOD_EXTERN)) ? 2 : 1;
79}
80
81static long long get_longlong(struct expression *expr)
82{
83	int no_expand = expr->ctype->ctype.modifiers & MOD_UNSIGNED;
84	long long mask = 1ULL << (expr->ctype->bit_size - 1);
85	long long value = expr->value;
86	long long ormask, andmask;
87
88	if (!(value & mask))
89		no_expand = 1;
90	andmask = mask | (mask-1);
91	ormask = ~andmask;
92	if (no_expand)
93		ormask = 0;
94	return (value & andmask) | ormask;
95}
96
97void cast_value(struct expression *expr, struct symbol *newtype,
98		struct expression *old, struct symbol *oldtype)
99{
100	int old_size = oldtype->bit_size;
101	int new_size = newtype->bit_size;
102	long long value, mask, signmask;
103	long long oldmask, oldsignmask, dropped;
104
105	if (is_float_type(newtype) || is_float_type(oldtype))
106		goto Float;
107
108	// For pointers and integers, we can just move the value around
109	expr->type = EXPR_VALUE;
110	expr->taint = old->taint;
111	if (old_size == new_size) {
112		expr->value = old->value;
113		return;
114	}
115
116	// expand it to the full "long long" value
117	value = get_longlong(old);
118
119Int:
120	// _Bool requires a zero test rather than truncation.
121	if (is_bool_type(newtype)) {
122		expr->value = !!value;
123		if (!conservative && value != 0 && value != 1)
124			warning(old->pos, "odd constant _Bool cast (%llx becomes 1)", value);
125		return;
126	}
127
128	// Truncate it to the new size
129	signmask = 1ULL << (new_size-1);
130	mask = signmask | (signmask-1);
131	expr->value = value & mask;
132
133	// Stop here unless checking for truncation
134	if (!Wcast_truncate || conservative)
135		return;
136
137	// Check if we dropped any bits..
138	oldsignmask = 1ULL << (old_size-1);
139	oldmask = oldsignmask | (oldsignmask-1);
140	dropped = oldmask & ~mask;
141
142	// OK if the bits were (and still are) purely sign bits
143	if (value & dropped) {
144		if (!(value & oldsignmask) || !(value & signmask) || (value & dropped) != dropped)
145			warning(old->pos, "cast truncates bits from constant value (%llx becomes %llx)",
146				value & oldmask,
147				value & mask);
148	}
149	return;
150
151Float:
152	if (!is_float_type(newtype)) {
153		value = (long long)old->fvalue;
154		expr->type = EXPR_VALUE;
155		expr->taint = 0;
156		goto Int;
157	}
158
159	if (!is_float_type(oldtype))
160		expr->fvalue = (long double)get_longlong(old);
161	else
162		expr->fvalue = old->fvalue;
163
164	if (newtype->rank <= 0) {
165		if (newtype->rank == 0)
166			expr->fvalue = (double)expr->fvalue;
167		else
168			expr->fvalue = (float)expr->fvalue;
169	}
170	expr->type = EXPR_FVALUE;
171}
172
173/* Return true if constant shift size is valid */
174static bool check_shift_count(struct expression *expr, struct expression *right)
175{
176	struct symbol *ctype = expr->ctype;
177	long long count = get_longlong(right);
178
179	if (count >= 0 && count < ctype->bit_size)
180		return true;
181	return false;
182}
183
184/*
185 * CAREFUL! We need to get the size and sign of the
186 * result right!
187 */
188#define CONVERT(op,s)	(((op)<<1)+(s))
189#define SIGNED(op)	CONVERT(op, 1)
190#define UNSIGNED(op)	CONVERT(op, 0)
191static int simplify_int_binop(struct expression *expr, struct symbol *ctype)
192{
193	struct expression *left = expr->left, *right = expr->right;
194	unsigned long long v, l, r, mask;
195	signed long long sl, sr;
196	int is_signed;
197
198	if (right->type != EXPR_VALUE)
199		return 0;
200	r = right->value;
201	if (expr->op == SPECIAL_LEFTSHIFT || expr->op == SPECIAL_RIGHTSHIFT) {
202		if (!check_shift_count(expr, right))
203			return 0;
204	}
205	if (left->type != EXPR_VALUE)
206		return 0;
207	l = left->value; r = right->value;
208	is_signed = !(ctype->ctype.modifiers & MOD_UNSIGNED);
209	mask = 1ULL << (ctype->bit_size-1);
210	sl = l; sr = r;
211	if (is_signed && (sl & mask))
212		sl |= ~(mask-1);
213	if (is_signed && (sr & mask))
214		sr |= ~(mask-1);
215
216	switch (CONVERT(expr->op,is_signed)) {
217	case SIGNED('+'):
218	case UNSIGNED('+'):
219		v = l + r;
220		break;
221
222	case SIGNED('-'):
223	case UNSIGNED('-'):
224		v = l - r;
225		break;
226
227	case SIGNED('&'):
228	case UNSIGNED('&'):
229		v = l & r;
230		break;
231
232	case SIGNED('|'):
233	case UNSIGNED('|'):
234		v = l | r;
235		break;
236
237	case SIGNED('^'):
238	case UNSIGNED('^'):
239		v = l ^ r;
240		break;
241
242	case SIGNED('*'):
243		v = sl * sr;
244		break;
245
246	case UNSIGNED('*'):
247		v = l * r;
248		break;
249
250	case SIGNED('/'):
251		if (!r)
252			goto Div;
253		if (l == mask && sr == -1)
254			goto Overflow;
255		v = sl / sr;
256		break;
257
258	case UNSIGNED('/'):
259		if (!r) goto Div;
260		v = l / r;
261		break;
262
263	case SIGNED('%'):
264		if (!r)
265			goto Div;
266		if (l == mask && sr == -1)
267			goto Overflow;
268		v = sl % sr;
269		break;
270
271	case UNSIGNED('%'):
272		if (!r) goto Div;
273		v = l % r;
274		break;
275
276	case SIGNED(SPECIAL_LEFTSHIFT):
277	case UNSIGNED(SPECIAL_LEFTSHIFT):
278		v = l << r;
279		break;
280
281	case SIGNED(SPECIAL_RIGHTSHIFT):
282		v = sl >> r;
283		break;
284
285	case UNSIGNED(SPECIAL_RIGHTSHIFT):
286		v = l >> r;
287		break;
288
289	default:
290		return 0;
291	}
292	mask = mask | (mask-1);
293	expr->value = v & mask;
294	expr->type = EXPR_VALUE;
295	expr->taint = left->taint | right->taint;
296	return 1;
297Div:
298	if (!conservative)
299		warning(expr->pos, "division by zero");
300	return 0;
301Overflow:
302	if (!conservative)
303		warning(expr->pos, "constant integer operation overflow");
304	return 0;
305}
306
307static int simplify_cmp_binop(struct expression *expr, struct symbol *ctype)
308{
309	struct expression *left = expr->left, *right = expr->right;
310	unsigned long long l, r, mask;
311	signed long long sl, sr;
312
313	if (left->type != EXPR_VALUE || right->type != EXPR_VALUE)
314		return 0;
315	l = left->value; r = right->value;
316	mask = 1ULL << (ctype->bit_size-1);
317	sl = l; sr = r;
318	if (sl & mask)
319		sl |= ~(mask-1);
320	if (sr & mask)
321		sr |= ~(mask-1);
322	switch (expr->op) {
323	case '<':		expr->value = sl < sr; break;
324	case '>':		expr->value = sl > sr; break;
325	case SPECIAL_LTE:	expr->value = sl <= sr; break;
326	case SPECIAL_GTE:	expr->value = sl >= sr; break;
327	case SPECIAL_EQUAL:	expr->value = l == r; break;
328	case SPECIAL_NOTEQUAL:	expr->value = l != r; break;
329	case SPECIAL_UNSIGNED_LT:expr->value = l < r; break;
330	case SPECIAL_UNSIGNED_GT:expr->value = l > r; break;
331	case SPECIAL_UNSIGNED_LTE:expr->value = l <= r; break;
332	case SPECIAL_UNSIGNED_GTE:expr->value = l >= r; break;
333	}
334	expr->type = EXPR_VALUE;
335	expr->taint = left->taint | right->taint;
336	return 1;
337}
338
339static int simplify_float_binop(struct expression *expr)
340{
341	struct expression *left = expr->left, *right = expr->right;
342	int rank = expr->ctype->rank;
343	long double l, r, res;
344
345	if (left->type != EXPR_FVALUE || right->type != EXPR_FVALUE)
346		return 0;
347
348	l = left->fvalue;
349	r = right->fvalue;
350
351	if (rank > 0) {
352		switch (expr->op) {
353		case '+':	res = l + r; break;
354		case '-':	res = l - r; break;
355		case '*':	res = l * r; break;
356		case '/':	if (!r) goto Div;
357				res = l / r; break;
358		default: return 0;
359		}
360	} else if (rank == 0) {
361		switch (expr->op) {
362		case '+':	res = (double) l + (double) r; break;
363		case '-':	res = (double) l - (double) r; break;
364		case '*':	res = (double) l * (double) r; break;
365		case '/':	if (!r) goto Div;
366				res = (double) l / (double) r; break;
367		default: return 0;
368		}
369	} else {
370		switch (expr->op) {
371		case '+':	res = (float)l + (float)r; break;
372		case '-':	res = (float)l - (float)r; break;
373		case '*':	res = (float)l * (float)r; break;
374		case '/':	if (!r) goto Div;
375				res = (float)l / (float)r; break;
376		default: return 0;
377		}
378	}
379	expr->type = EXPR_FVALUE;
380	expr->fvalue = res;
381	return 1;
382Div:
383	if (!conservative)
384		warning(expr->pos, "division by zero");
385	return 0;
386}
387
388static int simplify_float_cmp(struct expression *expr, struct symbol *ctype)
389{
390	struct expression *left = expr->left, *right = expr->right;
391	long double l, r;
392
393	if (left->type != EXPR_FVALUE || right->type != EXPR_FVALUE)
394		return 0;
395
396	l = left->fvalue;
397	r = right->fvalue;
398	switch (expr->op) {
399	case '<':		expr->value = l < r; break;
400	case '>':		expr->value = l > r; break;
401	case SPECIAL_LTE:	expr->value = l <= r; break;
402	case SPECIAL_GTE:	expr->value = l >= r; break;
403	case SPECIAL_EQUAL:	expr->value = l == r; break;
404	case SPECIAL_NOTEQUAL:	expr->value = l != r; break;
405	}
406	expr->type = EXPR_VALUE;
407	expr->taint = 0;
408	return 1;
409}
410
411static int expand_binop(struct expression *expr)
412{
413	int cost;
414
415	cost = expand_expression(expr->left);
416	cost += expand_expression(expr->right);
417	if (simplify_int_binop(expr, expr->ctype))
418		return 0;
419	if (simplify_float_binop(expr))
420		return 0;
421	return cost + 1;
422}
423
424static int expand_logical(struct expression *expr)
425{
426	struct expression *left = expr->left;
427	struct expression *right;
428	int cost, rcost;
429
430	/* Do immediate short-circuiting ... */
431	cost = expand_expression(left);
432	if (left->type == EXPR_VALUE) {
433		if (expr->op == SPECIAL_LOGICAL_AND) {
434			if (!left->value) {
435				expr->type = EXPR_VALUE;
436				expr->value = 0;
437				expr->taint = left->taint;
438				return 0;
439			}
440		} else {
441			if (left->value) {
442				expr->type = EXPR_VALUE;
443				expr->value = 1;
444				expr->taint = left->taint;
445				return 0;
446			}
447		}
448	}
449
450	right = expr->right;
451	rcost = expand_expression(right);
452	if (left->type == EXPR_VALUE && right->type == EXPR_VALUE) {
453		/*
454		 * We know the left value doesn't matter, since
455		 * otherwise we would have short-circuited it..
456		 */
457		expr->type = EXPR_VALUE;
458		expr->value = right->value != 0;
459		expr->taint = left->taint | right->taint;
460		return 0;
461	}
462
463	/*
464	 * If the right side is safe and cheaper than a branch,
465	 * just avoid the branch and turn it into a regular binop
466	 * style SAFELOGICAL.
467	 */
468	if (rcost < BRANCH_COST) {
469		expr->type = EXPR_BINOP;
470		rcost -= BRANCH_COST - 1;
471	}
472
473	return cost + BRANCH_COST + rcost;
474}
475
476static int expand_comma(struct expression *expr)
477{
478	int cost;
479
480	cost = expand_expression(expr->left);
481	cost += expand_expression(expr->right);
482	if (expr->left->type == EXPR_VALUE || expr->left->type == EXPR_FVALUE) {
483		unsigned flags = expr->flags;
484		unsigned taint;
485		taint = expr->left->type == EXPR_VALUE ? expr->left->taint : 0;
486		*expr = *expr->right;
487		expr->flags = flags;
488		if (expr->type == EXPR_VALUE)
489			expr->taint |= Taint_comma | taint;
490	}
491	return cost;
492}
493
494#define MOD_IGN (MOD_QUALIFIER)
495
496static int compare_types(int op, struct symbol *left, struct symbol *right)
497{
498	struct ctype c1 = {.base_type = left};
499	struct ctype c2 = {.base_type = right};
500	switch (op) {
501	case SPECIAL_EQUAL:
502		return !type_difference(&c1, &c2, MOD_IGN, MOD_IGN);
503	case SPECIAL_NOTEQUAL:
504		return type_difference(&c1, &c2, MOD_IGN, MOD_IGN) != NULL;
505	case '<':
506		return left->bit_size < right->bit_size;
507	case '>':
508		return left->bit_size > right->bit_size;
509	case SPECIAL_LTE:
510		return left->bit_size <= right->bit_size;
511	case SPECIAL_GTE:
512		return left->bit_size >= right->bit_size;
513	}
514	return 0;
515}
516
517static int expand_compare(struct expression *expr)
518{
519	struct expression *left = expr->left, *right = expr->right;
520	int cost;
521
522	cost = expand_expression(left);
523	cost += expand_expression(right);
524
525	if (left && right) {
526		/* Type comparison? */
527		if (left->type == EXPR_TYPE && right->type == EXPR_TYPE) {
528			int op = expr->op;
529			expr->type = EXPR_VALUE;
530			expr->value = compare_types(op, left->symbol, right->symbol);
531			expr->taint = 0;
532			return 0;
533		}
534		if (simplify_cmp_binop(expr, left->ctype))
535			return 0;
536		if (simplify_float_cmp(expr, left->ctype))
537			return 0;
538	}
539	return cost + 1;
540}
541
542static int expand_conditional(struct expression *expr)
543{
544	struct expression *cond = expr->conditional;
545	struct expression *valt = expr->cond_true;
546	struct expression *valf = expr->cond_false;
547	int cost, cond_cost;
548
549	cond_cost = expand_expression(cond);
550	if (cond->type == EXPR_VALUE) {
551		unsigned flags = expr->flags;
552		if (!cond->value)
553			valt = valf;
554		if (!valt)
555			valt = cond;
556		cost = expand_expression(valt);
557		*expr = *valt;
558		expr->flags = flags;
559		if (expr->type == EXPR_VALUE)
560			expr->taint |= cond->taint;
561		return cost;
562	}
563
564	cost = expand_expression(valt);
565	cost += expand_expression(valf);
566
567	if (cost < SELECT_COST) {
568		expr->type = EXPR_SELECT;
569		cost -= BRANCH_COST - 1;
570	}
571
572	return cost + cond_cost + BRANCH_COST;
573}
574
575static void check_assignment(struct expression *expr)
576{
577	struct expression *right;
578
579	switch (expr->op) {
580	case SPECIAL_SHL_ASSIGN:
581	case SPECIAL_SHR_ASSIGN:
582		right = expr->right;
583		if (right->type != EXPR_VALUE)
584			break;
585		check_shift_count(expr, right);
586		break;
587	}
588	return;
589}
590
591static int expand_assignment(struct expression *expr)
592{
593	expand_expression(expr->left);
594	expand_expression(expr->right);
595
596	if (!conservative)
597		check_assignment(expr);
598	return SIDE_EFFECTS;
599}
600
601static int expand_addressof(struct expression *expr)
602{
603	return expand_expression(expr->unop);
604}
605
606///
607// lookup the type of a struct's memeber at the requested offset
608static struct symbol *find_member(struct symbol *sym, int offset)
609{
610	struct ptr_list *head, *list;
611
612	head = (struct ptr_list *) sym->symbol_list;
613	list = head;
614	if (!head)
615		return NULL;
616	do {
617		int nr = list->nr;
618		int i;
619		for (i = 0; i < nr; i++) {
620			struct symbol *ent = (struct symbol *) list->list[i];
621			int curr = ent->offset;
622			if (curr == offset)
623				return ent;
624			if (curr > offset)
625				return NULL;
626		}
627	} while ((list = list->next) != head);
628	return NULL;
629}
630
631///
632// lookup a suitable default initializer value at the requested offset
633static struct expression *default_initializer(struct symbol *sym, int offset)
634{
635	static struct expression value;
636	struct symbol *type;
637
638redo:
639	switch (sym->type) {
640	case SYM_NODE:
641		sym = sym->ctype.base_type;
642		goto redo;
643	case SYM_STRUCT:
644		type = find_member(sym, offset);
645		if (!type)
646			return NULL;
647		break;
648	case SYM_ARRAY:
649		type = sym->ctype.base_type;
650		break;
651	default:
652		return NULL;
653	}
654
655	if (is_integral_type(type))
656		value.type = EXPR_VALUE;
657	else if (is_float_type(type))
658		value.type = EXPR_FVALUE;
659	else
660		return NULL;
661
662	value.ctype = type;
663	return &value;
664}
665
666/*
667 * Look up a trustable initializer value at the requested offset.
668 *
669 * Return NULL if no such value can be found or statically trusted.
670 */
671static struct expression *constant_symbol_value(struct symbol *sym, int offset)
672{
673	struct expression *value;
674
675	if (sym->ctype.modifiers & MOD_ACCESS)
676		return NULL;
677	value = sym->initializer;
678	if (!value)
679		return NULL;
680	if (value->type == EXPR_INITIALIZER) {
681		struct expression *entry;
682		FOR_EACH_PTR(value->expr_list, entry) {
683			if (entry->type != EXPR_POS) {
684				if (offset)
685					continue;
686				return entry;
687			}
688			if (entry->init_offset < offset)
689				continue;
690			if (entry->init_offset > offset)
691				break;
692			return entry->init_expr;
693		} END_FOR_EACH_PTR(entry);
694
695		value = default_initializer(sym, offset);
696	}
697	return value;
698}
699
700static int expand_dereference(struct expression *expr)
701{
702	struct expression *unop = expr->unop;
703	unsigned int offset;
704
705	expand_expression(unop);
706
707	/*
708	 * NOTE! We get a bogus warning right now for some special
709	 * cases: apparently I've screwed up the optimization of
710	 * a zero-offset dereference, and the ctype is wrong.
711	 *
712	 * Leave the warning in anyway, since this is also a good
713	 * test for me to get the type evaluation right..
714	 */
715	if (expr->ctype->ctype.modifiers & MOD_NODEREF)
716		warning(unop->pos, "dereference of noderef expression");
717
718	/*
719	 * Is it "symbol" or "symbol + offset"?
720	 */
721	offset = 0;
722	while (unop->type == EXPR_BINOP && unop->op == '+') {
723		struct expression *right = unop->right;
724		if (right->type != EXPR_VALUE)
725			break;
726		offset += right->value;
727		unop = unop->left;
728	}
729
730	if (unop->type == EXPR_SYMBOL) {
731		struct symbol *sym = unop->symbol;
732		struct symbol *ctype = expr->ctype;
733		struct expression *value = constant_symbol_value(sym, offset);
734
735		/* Const symbol with a constant initializer? */
736		if (value && value->ctype) {
737			if (ctype->bit_size != value->ctype->bit_size)
738				return UNSAFE;
739			if (value->type == EXPR_VALUE) {
740				if (!is_integral_type(ctype))
741					return UNSAFE;
742				if (is_bitfield_type(value->ctype))
743					return UNSAFE;
744				expr->type = EXPR_VALUE;
745				expr->value = value->value;
746				expr->taint = 0;
747				return 0;
748			} else if (value->type == EXPR_FVALUE) {
749				if (!is_float_type(ctype))
750					return UNSAFE;
751				expr->type = EXPR_FVALUE;
752				expr->fvalue = value->fvalue;
753				return 0;
754			}
755		}
756
757		/* Direct symbol dereference? Cheap and safe */
758		return (sym->ctype.modifiers & (MOD_STATIC | MOD_EXTERN)) ? 2 : 1;
759	}
760
761	return UNSAFE;
762}
763
764static int simplify_preop(struct expression *expr)
765{
766	struct expression *op = expr->unop;
767	unsigned long long v, mask;
768
769	if (op->type != EXPR_VALUE)
770		return 0;
771
772	mask = 1ULL << (expr->ctype->bit_size-1);
773	v = op->value;
774	switch (expr->op) {
775	case '+': break;
776	case '-':
777		if (v == mask && !(expr->ctype->ctype.modifiers & MOD_UNSIGNED))
778			goto Overflow;
779		v = -v;
780		break;
781	case '!': v = !v; break;
782	case '~': v = ~v; break;
783	default: return 0;
784	}
785	mask = mask | (mask-1);
786	expr->value = v & mask;
787	expr->type = EXPR_VALUE;
788	expr->taint = op->taint;
789	return 1;
790
791Overflow:
792	if (!conservative)
793		warning(expr->pos, "constant integer operation overflow");
794	return 0;
795}
796
797static int simplify_float_preop(struct expression *expr)
798{
799	struct expression *op = expr->unop;
800	long double v;
801
802	if (op->type != EXPR_FVALUE)
803		return 0;
804	v = op->fvalue;
805	switch (expr->op) {
806	case '+': break;
807	case '-': v = -v; break;
808	default: return 0;
809	}
810	expr->fvalue = v;
811	expr->type = EXPR_FVALUE;
812	return 1;
813}
814
815/*
816 * Unary post-ops: x++ and x--
817 */
818static int expand_postop(struct expression *expr)
819{
820	expand_expression(expr->unop);
821	return SIDE_EFFECTS;
822}
823
824static int expand_preop(struct expression *expr)
825{
826	int cost;
827
828	switch (expr->op) {
829	case '*':
830		return expand_dereference(expr);
831
832	case '&':
833		return expand_addressof(expr);
834
835	case SPECIAL_INCREMENT:
836	case SPECIAL_DECREMENT:
837		/*
838		 * From a type evaluation standpoint the preops are
839		 * the same as the postops
840		 */
841		return expand_postop(expr);
842
843	default:
844		break;
845	}
846	cost = expand_expression(expr->unop);
847
848	if (simplify_preop(expr))
849		return 0;
850	if (simplify_float_preop(expr))
851		return 0;
852	return cost + 1;
853}
854
855static int expand_arguments(struct expression_list *head)
856{
857	int cost = 0;
858	struct expression *expr;
859
860	FOR_EACH_PTR (head, expr) {
861		cost += expand_expression(expr);
862	} END_FOR_EACH_PTR(expr);
863	return cost;
864}
865
866static int expand_cast(struct expression *expr)
867{
868	int cost;
869	struct expression *target = expr->cast_expression;
870
871	cost = expand_expression(target);
872
873	/* Simplify normal integer casts.. */
874	if (target->type == EXPR_VALUE || target->type == EXPR_FVALUE) {
875		cast_value(expr, expr->ctype, target, target->ctype);
876		return 0;
877	}
878	return cost + 1;
879}
880
881/*
882 * expand a call expression with a symbol. This
883 * should expand builtins.
884 */
885static int expand_symbol_call(struct expression *expr, int cost)
886{
887	struct expression *fn = expr->fn;
888	struct symbol *ctype = fn->ctype;
889
890	expand_expression(fn);
891
892	if (fn->type != EXPR_PREOP)
893		return SIDE_EFFECTS;
894
895	if (ctype->ctype.modifiers & MOD_INLINE) {
896		struct symbol *def;
897
898		def = ctype->definition ? ctype->definition : ctype;
899		if (inline_function(expr, def)) {
900			struct symbol *fn = def->ctype.base_type;
901			struct symbol *curr = current_fn;
902
903			current_fn = def;
904			evaluate_statement(expr->statement);
905			current_fn = curr;
906
907			fn->expanding = 1;
908			cost = expand_expression(expr);
909			fn->expanding = 0;
910			return cost;
911		}
912	}
913
914	if (ctype->op && ctype->op->expand)
915		return ctype->op->expand(expr, cost);
916
917	if (ctype->ctype.modifiers & MOD_PURE)
918		return cost + 1;
919
920	return SIDE_EFFECTS;
921}
922
923static int expand_call(struct expression *expr)
924{
925	int cost;
926	struct symbol *sym;
927	struct expression *fn = expr->fn;
928
929	cost = expand_arguments(expr->args);
930	sym = fn->ctype;
931	if (!sym) {
932		expression_error(expr, "function has no type");
933		return SIDE_EFFECTS;
934	}
935	if (sym->type == SYM_NODE)
936		return expand_symbol_call(expr, cost);
937
938	return SIDE_EFFECTS;
939}
940
941static int expand_expression_list(struct expression_list *list)
942{
943	int cost = 0;
944	struct expression *expr;
945
946	FOR_EACH_PTR(list, expr) {
947		cost += expand_expression(expr);
948	} END_FOR_EACH_PTR(expr);
949	return cost;
950}
951
952/*
953 * We can simplify nested position expressions if
954 * this is a simple (single) positional expression.
955 */
956static int expand_pos_expression(struct expression *expr)
957{
958	struct expression *nested = expr->init_expr;
959	unsigned long offset = expr->init_offset;
960	int nr = expr->init_nr;
961
962	if (nr == 1) {
963		switch (nested->type) {
964		case EXPR_POS:
965			offset += nested->init_offset;
966			*expr = *nested;
967			expr->init_offset = offset;
968			nested = expr;
969			break;
970
971		case EXPR_INITIALIZER: {
972			struct expression *reuse = nested, *entry;
973			*expr = *nested;
974			FOR_EACH_PTR(expr->expr_list, entry) {
975				if (entry->type == EXPR_POS) {
976					entry->init_offset += offset;
977				} else {
978					if (!reuse) {
979						/*
980						 * This happens rarely, but it can happen
981						 * with bitfields that are all at offset
982						 * zero..
983						 */
984						reuse = alloc_expression(entry->pos, EXPR_POS);
985					}
986					reuse->type = EXPR_POS;
987					reuse->ctype = entry->ctype;
988					reuse->init_offset = offset;
989					reuse->init_nr = 1;
990					reuse->init_expr = entry;
991					REPLACE_CURRENT_PTR(entry, reuse);
992					reuse = NULL;
993				}
994			} END_FOR_EACH_PTR(entry);
995			nested = expr;
996			break;
997		}
998
999		default:
1000			break;
1001		}
1002	}
1003	return expand_expression(nested);
1004}
1005
1006static unsigned long bit_offset(const struct expression *expr)
1007{
1008	unsigned long offset = 0;
1009	while (expr->type == EXPR_POS) {
1010		offset += bytes_to_bits(expr->init_offset);
1011		expr = expr->init_expr;
1012	}
1013	if (expr && expr->ctype)
1014		offset += expr->ctype->bit_offset;
1015	return offset;
1016}
1017
1018static unsigned long bit_range(const struct expression *expr)
1019{
1020	unsigned long range = 0;
1021	unsigned long size = 0;
1022	while (expr->type == EXPR_POS) {
1023		unsigned long nr = expr->init_nr;
1024		size = expr->ctype->bit_size;
1025		range += (nr - 1) * size;
1026		expr = expr->init_expr;
1027	}
1028	range += size;
1029	return range;
1030}
1031
1032static int compare_expressions(const void *_a, const void *_b)
1033{
1034	const struct expression *a = _a;
1035	const struct expression *b = _b;
1036	unsigned long a_pos = bit_offset(a);
1037	unsigned long b_pos = bit_offset(b);
1038
1039	return (a_pos < b_pos) ? -1 : (a_pos == b_pos) ? 0 : 1;
1040}
1041
1042static void sort_expression_list(struct expression_list **list)
1043{
1044	sort_list((struct ptr_list **)list, compare_expressions);
1045}
1046
1047static void verify_nonoverlapping(struct expression_list **list, struct expression *expr)
1048{
1049	struct expression *a = NULL;
1050	unsigned long max = 0;
1051	unsigned long whole = expr->ctype->bit_size;
1052	struct expression *b;
1053
1054	if (!Woverride_init)
1055		return;
1056
1057	FOR_EACH_PTR(*list, b) {
1058		unsigned long off, end;
1059		if (!b->ctype || !b->ctype->bit_size)
1060			continue;
1061		off = bit_offset(b);
1062		if (a && off < max) {
1063			warning(a->pos, "Initializer entry defined twice");
1064			info(b->pos, "  also defined here");
1065			if (!Woverride_init_all)
1066				return;
1067		}
1068		end = off + bit_range(b);
1069		if (!a && !Woverride_init_whole_range) {
1070			// If first entry is the whole range, do not let
1071			// any warning about it (this allow to initialize
1072			// an array with some default value and then override
1073			// some specific entries).
1074			if (off == 0 && end == whole)
1075				continue;
1076		}
1077		if (end > max) {
1078			max = end;
1079			a = b;
1080		}
1081	} END_FOR_EACH_PTR(b);
1082}
1083
1084static int expand_expression(struct expression *expr)
1085{
1086	if (!expr)
1087		return 0;
1088	if (!expr->ctype || expr->ctype == &bad_ctype)
1089		return UNSAFE;
1090
1091	switch (expr->type) {
1092	case EXPR_VALUE:
1093	case EXPR_FVALUE:
1094	case EXPR_STRING:
1095		return 0;
1096	case EXPR_TYPE:
1097	case EXPR_SYMBOL:
1098		return expand_symbol_expression(expr);
1099	case EXPR_BINOP:
1100		return expand_binop(expr);
1101
1102	case EXPR_LOGICAL:
1103		return expand_logical(expr);
1104
1105	case EXPR_COMMA:
1106		return expand_comma(expr);
1107
1108	case EXPR_COMPARE:
1109		return expand_compare(expr);
1110
1111	case EXPR_ASSIGNMENT:
1112		return expand_assignment(expr);
1113
1114	case EXPR_PREOP:
1115		return expand_preop(expr);
1116
1117	case EXPR_POSTOP:
1118		return expand_postop(expr);
1119
1120	case EXPR_CAST:
1121	case EXPR_FORCE_CAST:
1122	case EXPR_IMPLIED_CAST:
1123		return expand_cast(expr);
1124
1125	case EXPR_CALL:
1126		return expand_call(expr);
1127
1128	case EXPR_DEREF:
1129		warning(expr->pos, "we should not have an EXPR_DEREF left at expansion time");
1130		return UNSAFE;
1131
1132	case EXPR_SELECT:
1133	case EXPR_CONDITIONAL:
1134		return expand_conditional(expr);
1135
1136	case EXPR_STATEMENT: {
1137		struct statement *stmt = expr->statement;
1138		int cost = expand_statement(stmt);
1139
1140		if (stmt->type == STMT_EXPRESSION && stmt->expression)
1141			*expr = *stmt->expression;
1142		return cost;
1143	}
1144
1145	case EXPR_LABEL:
1146		return 0;
1147
1148	case EXPR_INITIALIZER:
1149		sort_expression_list(&expr->expr_list);
1150		verify_nonoverlapping(&expr->expr_list, expr);
1151		return expand_expression_list(expr->expr_list);
1152
1153	case EXPR_IDENTIFIER:
1154		return UNSAFE;
1155
1156	case EXPR_INDEX:
1157		return UNSAFE;
1158
1159	case EXPR_SLICE:
1160		return expand_expression(expr->base) + 1;
1161
1162	case EXPR_POS:
1163		return expand_pos_expression(expr);
1164
1165	case EXPR_GENERIC:
1166	case EXPR_SIZEOF:
1167	case EXPR_PTRSIZEOF:
1168	case EXPR_ALIGNOF:
1169	case EXPR_OFFSETOF:
1170		expression_error(expr, "internal front-end error: sizeof in expansion?");
1171		return UNSAFE;
1172	}
1173	return SIDE_EFFECTS;
1174}
1175
1176static void expand_const_expression(struct expression *expr, const char *where)
1177{
1178	if (expr) {
1179		expand_expression(expr);
1180		if (expr->type != EXPR_VALUE) {
1181			expression_error(expr, "Expected constant expression in %s", where);
1182			expr->ctype = &int_ctype;
1183			expr->type = EXPR_VALUE;
1184			expr->value = 0;
1185		}
1186	}
1187}
1188
1189int expand_symbol(struct symbol *sym)
1190{
1191	int retval;
1192	struct symbol *base_type;
1193
1194	if (!sym)
1195		return 0;
1196	base_type = sym->ctype.base_type;
1197	if (!base_type)
1198		return 0;
1199
1200	retval = expand_expression(sym->initializer);
1201	/* expand the body of the symbol */
1202	if (base_type->type == SYM_FN) {
1203		if (base_type->stmt)
1204			expand_statement(base_type->stmt);
1205	}
1206	return retval;
1207}
1208
1209static void expand_return_expression(struct statement *stmt)
1210{
1211	expand_expression(stmt->expression);
1212}
1213
1214static int expand_if_statement(struct statement *stmt)
1215{
1216	struct expression *expr = stmt->if_conditional;
1217
1218	if (!expr || !expr->ctype || expr->ctype == &bad_ctype)
1219		return UNSAFE;
1220
1221	expand_expression(expr);
1222
1223/* This is only valid if nobody jumps into the "dead" side */
1224#if 0
1225	/* Simplify constant conditionals without even evaluating the false side */
1226	if (expr->type == EXPR_VALUE) {
1227		struct statement *simple;
1228		simple = expr->value ? stmt->if_true : stmt->if_false;
1229
1230		/* Nothing? */
1231		if (!simple) {
1232			stmt->type = STMT_NONE;
1233			return 0;
1234		}
1235		expand_statement(simple);
1236		*stmt = *simple;
1237		return SIDE_EFFECTS;
1238	}
1239#endif
1240	expand_statement(stmt->if_true);
1241	expand_statement(stmt->if_false);
1242	return SIDE_EFFECTS;
1243}
1244
1245static int expand_asm_statement(struct statement *stmt)
1246{
1247	struct asm_operand *op;
1248	int cost = 0;
1249
1250	FOR_EACH_PTR(stmt->asm_outputs, op) {
1251		cost += expand_expression(op->expr);
1252	} END_FOR_EACH_PTR(op);
1253
1254	FOR_EACH_PTR(stmt->asm_inputs, op) {
1255		cost += expand_expression(op->expr);
1256	} END_FOR_EACH_PTR(op);
1257
1258	return cost;
1259}
1260
1261/*
1262 * Expanding a compound statement is really just
1263 * about adding up the costs of each individual
1264 * statement.
1265 *
1266 * We also collapse a simple compound statement:
1267 * this would trigger for simple inline functions,
1268 * except we would have to check the "return"
1269 * symbol usage. Next time.
1270 */
1271static int expand_compound(struct statement *stmt)
1272{
1273	struct statement *s, *last;
1274	int cost, statements;
1275
1276	if (stmt->ret)
1277		expand_symbol(stmt->ret);
1278
1279	last = stmt->args;
1280	cost = expand_statement(last);
1281	statements = last != NULL;
1282	FOR_EACH_PTR(stmt->stmts, s) {
1283		statements++;
1284		last = s;
1285		cost += expand_statement(s);
1286	} END_FOR_EACH_PTR(s);
1287
1288	if (statements == 1 && !stmt->ret)
1289		*stmt = *last;
1290
1291	return cost;
1292}
1293
1294static int expand_statement(struct statement *stmt)
1295{
1296	if (!stmt)
1297		return 0;
1298
1299	switch (stmt->type) {
1300	case STMT_DECLARATION: {
1301		struct symbol *sym;
1302		FOR_EACH_PTR(stmt->declaration, sym) {
1303			expand_symbol(sym);
1304		} END_FOR_EACH_PTR(sym);
1305		return SIDE_EFFECTS;
1306	}
1307
1308	case STMT_RETURN:
1309		expand_return_expression(stmt);
1310		return SIDE_EFFECTS;
1311
1312	case STMT_EXPRESSION:
1313		return expand_expression(stmt->expression);
1314
1315	case STMT_COMPOUND:
1316		return expand_compound(stmt);
1317
1318	case STMT_IF:
1319		return expand_if_statement(stmt);
1320
1321	case STMT_ITERATOR:
1322		expand_expression(stmt->iterator_pre_condition);
1323		expand_expression(stmt->iterator_post_condition);
1324		expand_statement(stmt->iterator_pre_statement);
1325		expand_statement(stmt->iterator_statement);
1326		expand_statement(stmt->iterator_post_statement);
1327		return SIDE_EFFECTS;
1328
1329	case STMT_SWITCH:
1330		expand_expression(stmt->switch_expression);
1331		expand_statement(stmt->switch_statement);
1332		return SIDE_EFFECTS;
1333
1334	case STMT_CASE:
1335		expand_const_expression(stmt->case_expression, "case statement");
1336		expand_const_expression(stmt->case_to, "case statement");
1337		expand_statement(stmt->case_statement);
1338		return SIDE_EFFECTS;
1339
1340	case STMT_LABEL:
1341		expand_statement(stmt->label_statement);
1342		return SIDE_EFFECTS;
1343
1344	case STMT_GOTO:
1345		expand_expression(stmt->goto_expression);
1346		return SIDE_EFFECTS;
1347
1348	case STMT_NONE:
1349		break;
1350	case STMT_ASM:
1351		expand_asm_statement(stmt);
1352		break;
1353	case STMT_CONTEXT:
1354		expand_expression(stmt->expression);
1355		break;
1356	case STMT_RANGE:
1357		expand_expression(stmt->range_expression);
1358		expand_expression(stmt->range_low);
1359		expand_expression(stmt->range_high);
1360		break;
1361	}
1362	return SIDE_EFFECTS;
1363}
1364
1365static inline int bad_integer_constant_expression(struct expression *expr)
1366{
1367	if (!(expr->flags & CEF_ICE))
1368		return 1;
1369	if (expr->taint & Taint_comma)
1370		return 1;
1371	return 0;
1372}
1373
1374static long long __get_expression_value(struct expression *expr, int strict)
1375{
1376	long long value, mask;
1377	struct symbol *ctype;
1378
1379	if (!expr)
1380		return 0;
1381	ctype = evaluate_expression(expr);
1382	if (!ctype) {
1383		expression_error(expr, "bad constant expression type");
1384		return 0;
1385	}
1386	expand_expression(expr);
1387	if (expr->type != EXPR_VALUE) {
1388		if (strict != 2)
1389			expression_error(expr, "bad constant expression");
1390		return 0;
1391	}
1392	if ((strict == 1) && bad_integer_constant_expression(expr)) {
1393		expression_error(expr, "bad integer constant expression");
1394		return 0;
1395	}
1396
1397	value = expr->value;
1398	mask = 1ULL << (ctype->bit_size-1);
1399
1400	if (value & mask) {
1401		while (ctype->type != SYM_BASETYPE)
1402			ctype = ctype->ctype.base_type;
1403		if (!(ctype->ctype.modifiers & MOD_UNSIGNED))
1404			value = value | mask | ~(mask-1);
1405	}
1406	return value;
1407}
1408
1409long long get_expression_value(struct expression *expr)
1410{
1411	return __get_expression_value(expr, 0);
1412}
1413
1414long long const_expression_value(struct expression *expr)
1415{
1416	return __get_expression_value(expr, 1);
1417}
1418
1419long long get_expression_value_silent(struct expression *expr)
1420{
1421
1422	return __get_expression_value(expr, 2);
1423}
1424
1425int expr_truth_value(struct expression *expr)
1426{
1427	const int saved = conservative;
1428	struct symbol *ctype;
1429
1430	if (!expr)
1431		return 0;
1432
1433	ctype = evaluate_expression(expr);
1434	if (!ctype)
1435		return -1;
1436
1437	conservative = 1;
1438	expand_expression(expr);
1439	conservative = saved;
1440
1441redo:
1442	switch (expr->type) {
1443	case EXPR_COMMA:
1444		expr = expr->right;
1445		goto redo;
1446	case EXPR_VALUE:
1447		return expr->value != 0;
1448	case EXPR_FVALUE:
1449		return expr->fvalue != 0;
1450	default:
1451		return -1;
1452	}
1453}
1454
1455int is_zero_constant(struct expression *expr)
1456{
1457	const int saved = conservative;
1458	conservative = 1;
1459	expand_expression(expr);
1460	conservative = saved;
1461	return expr->type == EXPR_VALUE && !expr->value;
1462}
1463