11f5207b7SJohn Levon #ifndef EXPRESSION_H 21f5207b7SJohn Levon #define EXPRESSION_H 31f5207b7SJohn Levon /* 41f5207b7SJohn Levon * sparse/expression.h 51f5207b7SJohn Levon * 61f5207b7SJohn Levon * Copyright (C) 2003 Transmeta Corp. 71f5207b7SJohn Levon * 2003 Linus Torvalds 81f5207b7SJohn Levon * 91f5207b7SJohn Levon * Permission is hereby granted, free of charge, to any person obtaining a copy 101f5207b7SJohn Levon * of this software and associated documentation files (the "Software"), to deal 111f5207b7SJohn Levon * in the Software without restriction, including without limitation the rights 121f5207b7SJohn Levon * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 131f5207b7SJohn Levon * copies of the Software, and to permit persons to whom the Software is 141f5207b7SJohn Levon * furnished to do so, subject to the following conditions: 151f5207b7SJohn Levon * 161f5207b7SJohn Levon * The above copyright notice and this permission notice shall be included in 171f5207b7SJohn Levon * all copies or substantial portions of the Software. 181f5207b7SJohn Levon * 191f5207b7SJohn Levon * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 201f5207b7SJohn Levon * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 211f5207b7SJohn Levon * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 221f5207b7SJohn Levon * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 231f5207b7SJohn Levon * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 241f5207b7SJohn Levon * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 251f5207b7SJohn Levon * THE SOFTWARE. 261f5207b7SJohn Levon * 271f5207b7SJohn Levon * Declarations and helper functions for expression parsing. 281f5207b7SJohn Levon */ 291f5207b7SJohn Levon 301f5207b7SJohn Levon #include "allocate.h" 311f5207b7SJohn Levon #include "lib.h" 321f5207b7SJohn Levon #include "symbol.h" 331f5207b7SJohn Levon 341f5207b7SJohn Levon struct expression_list; 351f5207b7SJohn Levon 361f5207b7SJohn Levon enum expression_type { 371f5207b7SJohn Levon EXPR_VALUE = 1, 381f5207b7SJohn Levon EXPR_STRING, 391f5207b7SJohn Levon EXPR_SYMBOL, 401f5207b7SJohn Levon EXPR_TYPE, 411f5207b7SJohn Levon EXPR_BINOP, 421f5207b7SJohn Levon EXPR_ASSIGNMENT, 431f5207b7SJohn Levon EXPR_LOGICAL, 441f5207b7SJohn Levon EXPR_DEREF, 451f5207b7SJohn Levon EXPR_PREOP, 461f5207b7SJohn Levon EXPR_POSTOP, 471f5207b7SJohn Levon EXPR_CAST, 481f5207b7SJohn Levon EXPR_FORCE_CAST, 491f5207b7SJohn Levon EXPR_IMPLIED_CAST, 501f5207b7SJohn Levon EXPR_SIZEOF, 511f5207b7SJohn Levon EXPR_ALIGNOF, 521f5207b7SJohn Levon EXPR_PTRSIZEOF, 531f5207b7SJohn Levon EXPR_CONDITIONAL, 541f5207b7SJohn Levon EXPR_SELECT, // a "safe" conditional expression 551f5207b7SJohn Levon EXPR_STATEMENT, 561f5207b7SJohn Levon EXPR_CALL, 571f5207b7SJohn Levon EXPR_COMMA, 581f5207b7SJohn Levon EXPR_COMPARE, 591f5207b7SJohn Levon EXPR_LABEL, 601f5207b7SJohn Levon EXPR_INITIALIZER, // initializer list 611f5207b7SJohn Levon EXPR_IDENTIFIER, // identifier in initializer 621f5207b7SJohn Levon EXPR_INDEX, // index in initializer 631f5207b7SJohn Levon EXPR_POS, // position in initializer 641f5207b7SJohn Levon EXPR_FVALUE, 651f5207b7SJohn Levon EXPR_SLICE, 661f5207b7SJohn Levon EXPR_OFFSETOF, 67*c85f09ccSJohn Levon EXPR_ASM_OPERAND, 681f5207b7SJohn Levon }; 691f5207b7SJohn Levon 701f5207b7SJohn Levon 711f5207b7SJohn Levon /* 721f5207b7SJohn Levon * Flags for tracking the promotion of constness related attributes 731f5207b7SJohn Levon * from subexpressions to their parents. 741f5207b7SJohn Levon * 751f5207b7SJohn Levon * The flags are not independent as one might imply another. 761f5207b7SJohn Levon * The implications are as follows: 771f5207b7SJohn Levon * - CEF_INT, CEF_ENUM and 781f5207b7SJohn Levon * CEF_CHAR imply CEF_ICE. 791f5207b7SJohn Levon * 801f5207b7SJohn Levon * Use the CEF_*_SET_MASK and CEF_*_CLEAR_MASK 811f5207b7SJohn Levon * helper macros defined below to set or clear one of these flags. 821f5207b7SJohn Levon */ 831f5207b7SJohn Levon enum constexpr_flag { 841f5207b7SJohn Levon CEF_NONE = 0, 851f5207b7SJohn Levon /* 861f5207b7SJohn Levon * A constant in the sense of [6.4.4]: 871f5207b7SJohn Levon * - Integer constant [6.4.4.1] 881f5207b7SJohn Levon * - Floating point constant [6.4.4.2] 891f5207b7SJohn Levon * - Enumeration constant [6.4.4.3] 901f5207b7SJohn Levon * - Character constant [6.4.4.4] 911f5207b7SJohn Levon */ 921f5207b7SJohn Levon CEF_INT = (1 << 0), 931f5207b7SJohn Levon CEF_FLOAT = (1 << 1), 941f5207b7SJohn Levon CEF_ENUM = (1 << 2), 951f5207b7SJohn Levon CEF_CHAR = (1 << 3), 961f5207b7SJohn Levon 971f5207b7SJohn Levon /* 981f5207b7SJohn Levon * A constant expression in the sense of [6.6]: 991f5207b7SJohn Levon * - integer constant expression [6.6(6)] 1001f5207b7SJohn Levon * - arithmetic constant expression [6.6(8)] 1011f5207b7SJohn Levon * - address constant [6.6(9)] 1021f5207b7SJohn Levon */ 1031f5207b7SJohn Levon CEF_ICE = (1 << 4), 1041f5207b7SJohn Levon CEF_ACE = (1 << 5), 1051f5207b7SJohn Levon CEF_ADDR = (1 << 6), 1061f5207b7SJohn Levon 1071f5207b7SJohn Levon /* integer constant expression => arithmetic constant expression */ 1081f5207b7SJohn Levon CEF_SET_ICE = (CEF_ICE | CEF_ACE), 1091f5207b7SJohn Levon 1101f5207b7SJohn Levon /* integer constant => integer constant expression */ 1111f5207b7SJohn Levon CEF_SET_INT = (CEF_INT | CEF_SET_ICE), 1121f5207b7SJohn Levon 1131f5207b7SJohn Levon /* floating point constant => arithmetic constant expression */ 1141f5207b7SJohn Levon CEF_SET_FLOAT = (CEF_FLOAT | CEF_ACE), 1151f5207b7SJohn Levon 1161f5207b7SJohn Levon /* enumeration constant => integer constant expression */ 1171f5207b7SJohn Levon CEF_SET_ENUM = (CEF_ENUM | CEF_SET_ICE), 1181f5207b7SJohn Levon 1191f5207b7SJohn Levon /* character constant => integer constant expression */ 1201f5207b7SJohn Levon CEF_SET_CHAR = (CEF_CHAR | CEF_SET_ICE), 1211f5207b7SJohn Levon 1221f5207b7SJohn Levon /* 1231f5207b7SJohn Levon * Remove any "Constant" [6.4.4] flag, but retain the "constant 1241f5207b7SJohn Levon * expression" [6.6] flags. 1251f5207b7SJohn Levon */ 1261f5207b7SJohn Levon CEF_CONST_MASK = (CEF_INT | CEF_FLOAT | CEF_CHAR), 1271f5207b7SJohn Levon 1281f5207b7SJohn Levon /* 1291f5207b7SJohn Levon * not an integer constant expression => neither of integer, 1301f5207b7SJohn Levon * enumeration and character constant 1311f5207b7SJohn Levon */ 1321f5207b7SJohn Levon CEF_CLR_ICE = (CEF_ICE | CEF_INT | CEF_ENUM | CEF_CHAR), 1331f5207b7SJohn Levon }; 1341f5207b7SJohn Levon 1351f5207b7SJohn Levon enum { 1361f5207b7SJohn Levon Handled = 1 << 0, 1371f5207b7SJohn Levon Fake = 1 << 1, 1381f5207b7SJohn Levon }; /* for expr->flags */ 1391f5207b7SJohn Levon 1401f5207b7SJohn Levon enum { 1411f5207b7SJohn Levon Taint_comma = 1, 1421f5207b7SJohn Levon }; /* for expr->taint */ 1431f5207b7SJohn Levon 1441f5207b7SJohn Levon struct expression { 1451f5207b7SJohn Levon enum expression_type type:8; 1461f5207b7SJohn Levon unsigned flags:8; 1471f5207b7SJohn Levon unsigned smatch_flags:16; 1481f5207b7SJohn Levon int op; 1491f5207b7SJohn Levon struct position pos; 1501f5207b7SJohn Levon struct symbol *ctype; 1511f5207b7SJohn Levon unsigned long parent; 1521f5207b7SJohn Levon union { 1531f5207b7SJohn Levon // EXPR_VALUE 1541f5207b7SJohn Levon struct { 1551f5207b7SJohn Levon unsigned long long value; 1561f5207b7SJohn Levon unsigned taint; 1571f5207b7SJohn Levon }; 1581f5207b7SJohn Levon 1591f5207b7SJohn Levon // EXPR_FVALUE 1601f5207b7SJohn Levon long double fvalue; 1611f5207b7SJohn Levon 1621f5207b7SJohn Levon // EXPR_STRING 1631f5207b7SJohn Levon struct { 1641f5207b7SJohn Levon int wide; 1651f5207b7SJohn Levon struct string *string; 1661f5207b7SJohn Levon }; 1671f5207b7SJohn Levon 1681f5207b7SJohn Levon // EXPR_UNOP, EXPR_PREOP and EXPR_POSTOP 1691f5207b7SJohn Levon struct /* unop */ { 1701f5207b7SJohn Levon struct expression *unop; 1711f5207b7SJohn Levon unsigned long op_value; 1721f5207b7SJohn Levon }; 1731f5207b7SJohn Levon 1741f5207b7SJohn Levon // EXPR_SYMBOL, EXPR_TYPE 1751f5207b7SJohn Levon struct /* symbol_arg */ { 1761f5207b7SJohn Levon struct symbol *symbol; 1771f5207b7SJohn Levon struct ident *symbol_name; 1781f5207b7SJohn Levon }; 1791f5207b7SJohn Levon 1801f5207b7SJohn Levon // EXPR_STATEMENT 1811f5207b7SJohn Levon struct statement *statement; 1821f5207b7SJohn Levon 1831f5207b7SJohn Levon // EXPR_BINOP, EXPR_COMMA, EXPR_COMPARE, EXPR_LOGICAL and EXPR_ASSIGNMENT 1841f5207b7SJohn Levon struct /* binop_arg */ { 1851f5207b7SJohn Levon struct expression *left, *right; 1861f5207b7SJohn Levon }; 1871f5207b7SJohn Levon // EXPR_DEREF 1881f5207b7SJohn Levon struct /* deref_arg */ { 1891f5207b7SJohn Levon struct expression *deref; 1901f5207b7SJohn Levon struct ident *member; 1911f5207b7SJohn Levon int member_offset; 1921f5207b7SJohn Levon }; 1931f5207b7SJohn Levon // EXPR_SLICE 1941f5207b7SJohn Levon struct /* slice */ { 1951f5207b7SJohn Levon struct expression *base; 1961f5207b7SJohn Levon unsigned r_bitpos, r_nrbits; 1971f5207b7SJohn Levon }; 198*c85f09ccSJohn Levon // EXPR_CAST, EXPR_FORCE_CAST, EXPR_IMPLIED_CAST, 199*c85f09ccSJohn Levon // EXPR_SIZEOF, EXPR_ALIGNOF and EXPR_PTRSIZEOF 2001f5207b7SJohn Levon struct /* cast_arg */ { 2011f5207b7SJohn Levon struct symbol *cast_type; 2021f5207b7SJohn Levon struct expression *cast_expression; 2031f5207b7SJohn Levon }; 2041f5207b7SJohn Levon // EXPR_CONDITIONAL 2051f5207b7SJohn Levon // EXPR_SELECT 2061f5207b7SJohn Levon struct /* conditional_expr */ { 2071f5207b7SJohn Levon struct expression *conditional, *cond_true, *cond_false; 2081f5207b7SJohn Levon }; 2091f5207b7SJohn Levon // EXPR_CALL 2101f5207b7SJohn Levon struct /* call_expr */ { 2111f5207b7SJohn Levon struct expression *fn; 2121f5207b7SJohn Levon struct expression_list *args; 2131f5207b7SJohn Levon }; 2141f5207b7SJohn Levon // EXPR_LABEL 2151f5207b7SJohn Levon struct /* label_expr */ { 2161f5207b7SJohn Levon struct symbol *label_symbol; 2171f5207b7SJohn Levon }; 2181f5207b7SJohn Levon // EXPR_INITIALIZER 2191f5207b7SJohn Levon struct expression_list *expr_list; 2201f5207b7SJohn Levon // EXPR_IDENTIFIER 2211f5207b7SJohn Levon struct /* ident_expr */ { 2221f5207b7SJohn Levon int offset; 2231f5207b7SJohn Levon struct ident *expr_ident; 2241f5207b7SJohn Levon struct symbol *field; 2251f5207b7SJohn Levon struct expression *ident_expression; 2261f5207b7SJohn Levon }; 2271f5207b7SJohn Levon // EXPR_INDEX 2281f5207b7SJohn Levon struct /* index_expr */ { 2291f5207b7SJohn Levon unsigned int idx_from, idx_to; 2301f5207b7SJohn Levon struct expression *idx_expression; 2311f5207b7SJohn Levon }; 2321f5207b7SJohn Levon // EXPR_POS 2331f5207b7SJohn Levon struct /* initpos_expr */ { 2341f5207b7SJohn Levon unsigned int init_offset, init_nr; 2351f5207b7SJohn Levon struct expression *init_expr; 2361f5207b7SJohn Levon }; 2371f5207b7SJohn Levon // EXPR_OFFSETOF 2381f5207b7SJohn Levon struct { 2391f5207b7SJohn Levon struct symbol *in; 2401f5207b7SJohn Levon struct expression *down; 2411f5207b7SJohn Levon union { 2421f5207b7SJohn Levon struct ident *ident; 2431f5207b7SJohn Levon struct expression *index; 2441f5207b7SJohn Levon }; 2451f5207b7SJohn Levon }; 246*c85f09ccSJohn Levon // EXPR_ASM_OPERAND 247*c85f09ccSJohn Levon struct { 248*c85f09ccSJohn Levon struct ident *name; 249*c85f09ccSJohn Levon struct expression *constraint; 250*c85f09ccSJohn Levon struct expression *expr; 251*c85f09ccSJohn Levon }; 2521f5207b7SJohn Levon }; 2531f5207b7SJohn Levon }; 2541f5207b7SJohn Levon 255*c85f09ccSJohn Levon /// 256*c85f09ccSJohn Levon // Constant expression values 257*c85f09ccSJohn Levon // -------------------------- 258*c85f09ccSJohn Levon 259*c85f09ccSJohn Levon /// 260*c85f09ccSJohn Levon // test if an expression evaluates to the constant ``0``. 261*c85f09ccSJohn Levon // @return: ``1`` if @expr evaluate to ``0``, 262*c85f09ccSJohn Levon // ``0`` otherwise. 263*c85f09ccSJohn Levon int is_zero_constant(struct expression *expr); 264*c85f09ccSJohn Levon 265*c85f09ccSJohn Levon /// 266*c85f09ccSJohn Levon // test the compile time truth value of an expression 267*c85f09ccSJohn Levon // @return: 268*c85f09ccSJohn Levon // * ``-1`` if @expr is not constant, 269*c85f09ccSJohn Levon // * ``0`` or ``1`` depending on the truth value of @expr. 2701f5207b7SJohn Levon int expr_truth_value(struct expression *expr); 271*c85f09ccSJohn Levon 2721f5207b7SJohn Levon long long get_expression_value(struct expression *); 2731f5207b7SJohn Levon long long const_expression_value(struct expression *); 2741f5207b7SJohn Levon long long get_expression_value_silent(struct expression *expr); 2751f5207b7SJohn Levon 2761f5207b7SJohn Levon /* Expression parsing */ 2771f5207b7SJohn Levon struct token *parse_expression(struct token *token, struct expression **tree); 2781f5207b7SJohn Levon struct token *conditional_expression(struct token *token, struct expression **tree); 2791f5207b7SJohn Levon struct token *primary_expression(struct token *token, struct expression **tree); 2801f5207b7SJohn Levon struct token *parens_expression(struct token *token, struct expression **expr, const char *where); 2811f5207b7SJohn Levon struct token *assignment_expression(struct token *token, struct expression **tree); 2821f5207b7SJohn Levon 2831f5207b7SJohn Levon extern void evaluate_symbol_list(struct symbol_list *list); 2841f5207b7SJohn Levon extern struct symbol *evaluate_statement(struct statement *stmt); 2851f5207b7SJohn Levon extern struct symbol *evaluate_expression(struct expression *); 286efe51d0cSJohn Levon struct symbol *find_identifier(struct ident *ident, struct symbol_list *_list, int *offset); 2871f5207b7SJohn Levon 2881f5207b7SJohn Levon extern int expand_symbol(struct symbol *); 2891f5207b7SJohn Levon 2901f5207b7SJohn Levon static inline struct expression *alloc_expression(struct position pos, int type) 2911f5207b7SJohn Levon { 2921f5207b7SJohn Levon struct expression *expr = __alloc_expression(0); 2931f5207b7SJohn Levon expr->type = type; 2941f5207b7SJohn Levon expr->pos = pos; 2951f5207b7SJohn Levon expr->flags = CEF_NONE; 2961f5207b7SJohn Levon return expr; 2971f5207b7SJohn Levon } 2981f5207b7SJohn Levon 2991f5207b7SJohn Levon static inline struct expression *alloc_const_expression(struct position pos, int value) 3001f5207b7SJohn Levon { 3011f5207b7SJohn Levon struct expression *expr = __alloc_expression(0); 3021f5207b7SJohn Levon expr->type = EXPR_VALUE; 3031f5207b7SJohn Levon expr->pos = pos; 3041f5207b7SJohn Levon expr->value = value; 3051f5207b7SJohn Levon expr->ctype = &int_ctype; 3061f5207b7SJohn Levon expr->flags = CEF_SET_INT; 3071f5207b7SJohn Levon return expr; 3081f5207b7SJohn Levon } 3091f5207b7SJohn Levon 3101f5207b7SJohn Levon /* Type name parsing */ 3111f5207b7SJohn Levon struct token *typename(struct token *, struct symbol **, int *); 3121f5207b7SJohn Levon 3131f5207b7SJohn Levon static inline int lookup_type(struct token *token) 3141f5207b7SJohn Levon { 3151f5207b7SJohn Levon if (token->pos.type == TOKEN_IDENT) { 3161f5207b7SJohn Levon struct symbol *sym = lookup_symbol(token->ident, NS_SYMBOL | NS_TYPEDEF); 3171f5207b7SJohn Levon return sym && (sym->namespace & NS_TYPEDEF); 3181f5207b7SJohn Levon } 3191f5207b7SJohn Levon return 0; 3201f5207b7SJohn Levon } 3211f5207b7SJohn Levon 3221f5207b7SJohn Levon /* Statement parsing */ 3231f5207b7SJohn Levon struct statement *alloc_statement(struct position pos, int type); 3241f5207b7SJohn Levon struct token *initializer(struct expression **tree, struct token *token); 3251f5207b7SJohn Levon struct token *compound_statement(struct token *, struct statement *); 3261f5207b7SJohn Levon 3271f5207b7SJohn Levon /* The preprocessor calls this 'constant_expression()' */ 3281f5207b7SJohn Levon #define constant_expression(token,tree) conditional_expression(token, tree) 3291f5207b7SJohn Levon 3301f5207b7SJohn Levon /* Cast folding of constant values.. */ 3311f5207b7SJohn Levon void cast_value(struct expression *expr, struct symbol *newtype, 3321f5207b7SJohn Levon struct expression *old, struct symbol *oldtype); 3331f5207b7SJohn Levon 3341f5207b7SJohn Levon #endif 335