Avoid triggering a division by zero in the overflow check
[smatch.git] / linearize.h
blob61fbd8316d2aa97f3002cfc9658ead88d4d99dc2
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;
41 void *priv;
44 extern struct pseudo void_pseudo;
46 #define VOID (&void_pseudo)
48 struct multijmp {
49 struct basic_block *target;
50 int begin, end;
53 struct asm_constraint {
54 pseudo_t pseudo;
55 const char *constraint;
56 const struct ident *ident;
59 DECLARE_ALLOCATOR(asm_constraint);
60 DECLARE_PTR_LIST(asm_constraint_list, struct asm_constraint);
62 struct asm_rules {
63 struct asm_constraint_list *inputs;
64 struct asm_constraint_list *outputs;
65 struct asm_constraint_list *clobbers;
68 DECLARE_ALLOCATOR(asm_rules);
70 struct instruction {
71 unsigned opcode:8,
72 size:24;
73 struct basic_block *bb;
74 struct position pos;
75 struct symbol *type;
76 union {
77 pseudo_t target;
78 pseudo_t cond; /* for branch and switch */
80 union {
81 struct /* entrypoint */ {
82 struct pseudo_list *arg_list;
84 struct /* branch */ {
85 struct basic_block *bb_true, *bb_false;
87 struct /* switch */ {
88 struct multijmp_list *multijmp_list;
90 struct /* phi_node */ {
91 struct pseudo_list *phi_list;
93 struct /* phi source */ {
94 pseudo_t phi_src;
95 struct instruction_list *phi_users;
97 struct /* unops */ {
98 pseudo_t src;
99 struct symbol *orig_type; /* casts */
100 unsigned int offset; /* memops */
102 struct /* binops and sel */ {
103 pseudo_t src1, src2, src3;
105 struct /* slice */ {
106 pseudo_t base;
107 unsigned from, len;
109 struct /* multijump */ {
110 int begin, end;
112 struct /* setval */ {
113 pseudo_t symbol; /* Subtle: same offset as "src" !! */
114 struct expression *val;
116 struct /* call */ {
117 pseudo_t func;
118 struct pseudo_list *arguments;
119 struct symbol *fntype;
121 struct /* context */ {
122 int increment;
123 int check;
124 struct expression *context_expr;
126 struct /* asm */ {
127 const char *string;
128 struct asm_rules *asm_rules;
133 enum opcode {
134 OP_BADOP,
136 /* Entry */
137 OP_ENTRY,
139 /* Terminator */
140 OP_TERMINATOR,
141 OP_RET = OP_TERMINATOR,
142 OP_BR,
143 OP_SWITCH,
144 OP_INVOKE,
145 OP_COMPUTEDGOTO,
146 OP_UNWIND,
147 OP_TERMINATOR_END = OP_UNWIND,
149 /* Binary */
150 OP_BINARY,
151 OP_ADD = OP_BINARY,
152 OP_SUB,
153 OP_MULU, OP_MULS,
154 OP_DIVU, OP_DIVS,
155 OP_MODU, OP_MODS,
156 OP_SHL,
157 OP_LSR, OP_ASR,
159 /* Logical */
160 OP_AND,
161 OP_OR,
162 OP_XOR,
163 OP_AND_BOOL,
164 OP_OR_BOOL,
165 OP_BINARY_END = OP_OR_BOOL,
167 /* Binary comparison */
168 OP_BINCMP,
169 OP_SET_EQ = OP_BINCMP,
170 OP_SET_NE,
171 OP_SET_LE,
172 OP_SET_GE,
173 OP_SET_LT,
174 OP_SET_GT,
175 OP_SET_B,
176 OP_SET_A,
177 OP_SET_BE,
178 OP_SET_AE,
179 OP_BINCMP_END = OP_SET_AE,
181 /* Uni */
182 OP_NOT,
183 OP_NEG,
185 /* Select - three input values */
186 OP_SEL,
188 /* Memory */
189 OP_MALLOC,
190 OP_FREE,
191 OP_ALLOCA,
192 OP_LOAD,
193 OP_STORE,
194 OP_SETVAL,
195 OP_SYMADDR,
196 OP_GET_ELEMENT_PTR,
198 /* Other */
199 OP_PHI,
200 OP_PHISOURCE,
201 OP_CAST,
202 OP_SCAST,
203 OP_FPCAST,
204 OP_PTRCAST,
205 OP_INLINED_CALL,
206 OP_CALL,
207 OP_VANEXT,
208 OP_VAARG,
209 OP_SLICE,
210 OP_SNOP,
211 OP_LNOP,
212 OP_NOP,
213 OP_DEATHNOTE,
214 OP_ASM,
216 /* Sparse tagging (line numbers, context, whatever) */
217 OP_CONTEXT,
218 OP_RANGE,
220 /* Needed to translate SSA back to normal form */
221 OP_COPY,
224 struct basic_block_list;
225 struct instruction_list;
227 struct basic_block {
228 struct position pos;
229 unsigned long generation;
230 int context;
231 struct entrypoint *ep;
232 struct basic_block_list *parents; /* sources */
233 struct basic_block_list *children; /* destinations */
234 struct instruction_list *insns; /* Linear list of instructions */
235 struct pseudo_list *needs, *defines;
236 void *priv;
239 static inline int is_branch_goto(struct instruction *br)
241 return br && br->opcode==OP_BR && (!br->bb_true || !br->bb_false);
244 static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
246 add_ptr_list(list, bb);
249 static inline void add_instruction(struct instruction_list **list, struct instruction *insn)
251 add_ptr_list(list, insn);
254 static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp)
256 add_ptr_list(list, multijmp);
259 static inline pseudo_t *add_pseudo(struct pseudo_list **list, pseudo_t pseudo)
261 return add_ptr_list(list, pseudo);
264 static inline int remove_pseudo(struct pseudo_list **list, pseudo_t pseudo)
266 return delete_ptr_list_entry((struct ptr_list **)list, pseudo, 0) != 0;
269 static inline int bb_terminated(struct basic_block *bb)
271 struct instruction *insn;
272 if (!bb)
273 return 0;
274 insn = last_instruction(bb->insns);
275 return insn && insn->opcode >= OP_TERMINATOR
276 && insn->opcode <= OP_TERMINATOR_END;
279 static inline int bb_reachable(struct basic_block *bb)
281 return bb != NULL;
284 static inline void add_pseudo_ptr(pseudo_t *ptr, struct pseudo_ptr_list **list)
286 add_ptr_list(list, ptr);
289 static inline void add_pseudo_user_ptr(struct pseudo_user *user, struct pseudo_user_list **list)
291 add_ptr_list(list, user);
294 static inline int has_use_list(pseudo_t p)
296 return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_VAL);
299 static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp)
301 struct pseudo_user *user = __alloc_pseudo_user(0);
302 user->userp = pp;
303 user->insn = insn;
304 return user;
307 static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp)
309 *pp = p;
310 if (has_use_list(p))
311 add_pseudo_user_ptr(alloc_pseudo_user(insn, pp), &p->users);
314 static inline void remove_bb_from_list(struct basic_block_list **list, struct basic_block *entry, int count)
316 delete_ptr_list_entry((struct ptr_list **)list, entry, count);
319 static inline void replace_bb_in_list(struct basic_block_list **list,
320 struct basic_block *old, struct basic_block *new, int count)
322 replace_ptr_list_entry((struct ptr_list **)list, old, new, count);
325 struct entrypoint {
326 struct symbol *name;
327 struct symbol_list *syms;
328 struct pseudo_list *accesses;
329 struct basic_block_list *bbs;
330 struct basic_block *active;
331 struct instruction *entry;
334 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);
335 extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target);
337 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size);
338 pseudo_t alloc_pseudo(struct instruction *def);
339 pseudo_t value_pseudo(long long val);
341 struct entrypoint *linearize_symbol(struct symbol *sym);
342 int unssa(struct entrypoint *ep);
343 void show_entry(struct entrypoint *ep);
344 const char *show_pseudo(pseudo_t pseudo);
345 void show_bb(struct basic_block *bb);
346 const char *show_instruction(struct instruction *insn);
348 #endif /* LINEARIZE_H */