Avoid use of libc headers in the validation suite
[smatch.git] / linearize.h
blob7b2961bf2606b945a1f8e210ca9c985da0cd5435
1 #ifndef LINEARIZE_H
2 #define LINEARIZE_H
4 #include "lib.h"
5 #include "allocate.h"
6 #include "token.h"
7 #include "parse.h"
8 #include "symbol.h"
10 struct instruction;
11 DECLARE_PTR_LIST(pseudo_ptr_list, pseudo_t);
13 struct pseudo_user {
14 struct instruction *insn;
15 pseudo_t *userp;
18 DECLARE_ALLOCATOR(pseudo_user);
19 DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user);
22 enum pseudo_type {
23 PSEUDO_VOID,
24 PSEUDO_REG,
25 PSEUDO_SYM,
26 PSEUDO_VAL,
27 PSEUDO_ARG,
28 PSEUDO_PHI,
31 struct pseudo {
32 int nr;
33 enum pseudo_type type;
34 struct pseudo_user_list *users;
35 struct ident *ident;
36 union {
37 struct symbol *sym;
38 struct instruction *def;
39 long long value;
43 extern struct pseudo void_pseudo;
45 #define VOID (&void_pseudo)
47 struct multijmp {
48 struct basic_block *target;
49 int begin, end;
52 struct asm_constraint {
53 pseudo_t pseudo;
54 const char *constraint;
55 const struct ident *ident;
58 DECLARE_ALLOCATOR(asm_constraint);
59 DECLARE_PTR_LIST(asm_constraint_list, struct asm_constraint);
61 struct asm_rules {
62 struct asm_constraint_list *inputs;
63 struct asm_constraint_list *outputs;
64 struct asm_constraint_list *clobbers;
67 DECLARE_ALLOCATOR(asm_rules);
69 struct instruction {
70 unsigned opcode:8,
71 size:24;
72 struct basic_block *bb;
73 struct position pos;
74 union {
75 pseudo_t target;
76 pseudo_t cond; /* for branch and switch */
78 union {
79 struct /* entrypoint */ {
80 struct pseudo_list *arg_list;
82 struct /* branch */ {
83 struct basic_block *bb_true, *bb_false;
85 struct /* switch */ {
86 struct multijmp_list *multijmp_list;
88 struct /* phi_node */ {
89 struct pseudo_list *phi_list;
91 struct /* phi source */ {
92 pseudo_t phi_src;
93 struct instruction_list *phi_users;
95 struct /* unops */ {
96 pseudo_t src;
97 struct symbol *orig_type; /* casts */
98 unsigned int offset; /* memops */
100 struct /* binops and sel */ {
101 pseudo_t src1, src2, src3;
103 struct /* slice */ {
104 pseudo_t base;
105 unsigned from, len;
107 struct /* multijump */ {
108 int begin, end;
110 struct /* setval */ {
111 pseudo_t symbol; /* Subtle: same offset as "src" !! */
112 struct expression *val;
114 struct /* call */ {
115 pseudo_t func;
116 struct pseudo_list *arguments;
118 struct /* context */ {
119 int increment;
120 int check;
121 struct expression *context_expr;
123 struct /* asm */ {
124 const char *string;
125 struct asm_rules *asm_rules;
130 enum opcode {
131 OP_BADOP,
133 /* Entry */
134 OP_ENTRY,
136 /* Terminator */
137 OP_TERMINATOR,
138 OP_RET = OP_TERMINATOR,
139 OP_BR,
140 OP_SWITCH,
141 OP_INVOKE,
142 OP_COMPUTEDGOTO,
143 OP_UNWIND,
144 OP_TERMINATOR_END = OP_UNWIND,
146 /* Binary */
147 OP_BINARY,
148 OP_ADD = OP_BINARY,
149 OP_SUB,
150 OP_MULU, OP_MULS,
151 OP_DIVU, OP_DIVS,
152 OP_MODU, OP_MODS,
153 OP_SHL,
154 OP_LSR, OP_ASR,
156 /* Logical */
157 OP_AND,
158 OP_OR,
159 OP_XOR,
160 OP_AND_BOOL,
161 OP_OR_BOOL,
162 OP_BINARY_END = OP_OR_BOOL,
164 /* Binary comparison */
165 OP_BINCMP,
166 OP_SET_EQ = OP_BINCMP,
167 OP_SET_NE,
168 OP_SET_LE,
169 OP_SET_GE,
170 OP_SET_LT,
171 OP_SET_GT,
172 OP_SET_B,
173 OP_SET_A,
174 OP_SET_BE,
175 OP_SET_AE,
176 OP_BINCMP_END = OP_SET_AE,
178 /* Uni */
179 OP_NOT,
180 OP_NEG,
182 /* Select - three input values */
183 OP_SEL,
185 /* Memory */
186 OP_MALLOC,
187 OP_FREE,
188 OP_ALLOCA,
189 OP_LOAD,
190 OP_STORE,
191 OP_SETVAL,
192 OP_SYMADDR,
193 OP_GET_ELEMENT_PTR,
195 /* Other */
196 OP_PHI,
197 OP_PHISOURCE,
198 OP_CAST,
199 OP_SCAST,
200 OP_FPCAST,
201 OP_PTRCAST,
202 OP_INLINED_CALL,
203 OP_CALL,
204 OP_VANEXT,
205 OP_VAARG,
206 OP_SLICE,
207 OP_SNOP,
208 OP_LNOP,
209 OP_NOP,
210 OP_DEATHNOTE,
211 OP_ASM,
213 /* Sparse tagging (line numbers, context, whatever) */
214 OP_CONTEXT,
215 OP_RANGE,
217 /* Needed to translate SSA back to normal form */
218 OP_COPY,
221 struct basic_block_list;
222 struct instruction_list;
224 struct basic_block {
225 struct position pos;
226 unsigned long generation;
227 int context;
228 struct entrypoint *ep;
229 struct basic_block_list *parents; /* sources */
230 struct basic_block_list *children; /* destinations */
231 struct instruction_list *insns; /* Linear list of instructions */
232 struct pseudo_list *needs, *defines;
235 static inline int is_branch_goto(struct instruction *br)
237 return br && br->opcode==OP_BR && (!br->bb_true || !br->bb_false);
240 static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
242 add_ptr_list(list, bb);
245 static inline void add_instruction(struct instruction_list **list, struct instruction *insn)
247 add_ptr_list(list, insn);
250 static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp)
252 add_ptr_list(list, multijmp);
255 static inline pseudo_t *add_pseudo(struct pseudo_list **list, pseudo_t pseudo)
257 return add_ptr_list(list, pseudo);
260 static inline int remove_pseudo(struct pseudo_list **list, pseudo_t pseudo)
262 return delete_ptr_list_entry((struct ptr_list **)list, pseudo, 0) != 0;
265 static inline int bb_terminated(struct basic_block *bb)
267 struct instruction *insn;
268 if (!bb)
269 return 0;
270 insn = last_instruction(bb->insns);
271 return insn && insn->opcode >= OP_TERMINATOR
272 && insn->opcode <= OP_TERMINATOR_END;
275 static inline int bb_reachable(struct basic_block *bb)
277 return bb != NULL;
280 static inline void add_pseudo_ptr(pseudo_t *ptr, struct pseudo_ptr_list **list)
282 add_ptr_list(list, ptr);
285 static inline void add_pseudo_user_ptr(struct pseudo_user *user, struct pseudo_user_list **list)
287 add_ptr_list(list, user);
290 static inline int has_use_list(pseudo_t p)
292 return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_VAL);
295 static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp)
297 struct pseudo_user *user = __alloc_pseudo_user(0);
298 user->userp = pp;
299 user->insn = insn;
300 return user;
303 static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp)
305 *pp = p;
306 if (has_use_list(p))
307 add_pseudo_user_ptr(alloc_pseudo_user(insn, pp), &p->users);
310 static inline void remove_bb_from_list(struct basic_block_list **list, struct basic_block *entry, int count)
312 delete_ptr_list_entry((struct ptr_list **)list, entry, count);
315 static inline void replace_bb_in_list(struct basic_block_list **list,
316 struct basic_block *old, struct basic_block *new, int count)
318 replace_ptr_list_entry((struct ptr_list **)list, old, new, count);
321 struct entrypoint {
322 struct symbol *name;
323 struct symbol_list *syms;
324 struct pseudo_list *accesses;
325 struct basic_block_list *bbs;
326 struct basic_block *active;
327 struct instruction *entry;
330 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t true, pseudo_t false);
331 extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target);
333 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size);
334 pseudo_t alloc_pseudo(struct instruction *def);
335 pseudo_t value_pseudo(long long val);
337 struct entrypoint *linearize_symbol(struct symbol *sym);
338 int unssa(struct entrypoint *ep);
339 void show_entry(struct entrypoint *ep);
340 const char *show_pseudo(pseudo_t pseudo);
341 void show_bb(struct basic_block *bb);
342 const char *show_instruction(struct instruction *insn);
344 #endif /* LINEARIZE_H */