1 #ifndef LINEARIZE_H 2 #define LINEARIZE_H 3 4 #include "lib.h" 5 #include "allocate.h" 6 #include "token.h" 7 #include "parse.h" 8 #include "symbol.h" 9 10 struct instruction; 11 DECLARE_PTR_LIST(pseudo_ptr_list, pseudo_t); 12 13 struct pseudo_user { 14 struct instruction *insn; 15 pseudo_t *userp; 16 }; 17 18 DECLARE_ALLOCATOR(pseudo_user); 19 DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user); 20 21 22 enum pseudo_type { 23 PSEUDO_VOID, 24 PSEUDO_REG, 25 PSEUDO_SYM, 26 PSEUDO_VAL, 27 PSEUDO_ARG, 28 PSEUDO_PHI, 29 }; 30 31 struct pseudo { 32 int nr; 33 int size:16; /* OP_SETVAL only */ 34 enum pseudo_type type:8; 35 struct pseudo_user_list *users; 36 struct ident *ident; 37 union { 38 struct symbol *sym; 39 struct instruction *def; 40 long long value; 41 }; 42 void *priv; 43 }; 44 45 extern struct pseudo void_pseudo; 46 47 #define VOID (&void_pseudo) 48 49 struct multijmp { 50 struct basic_block *target; 51 int begin, end; 52 }; 53 54 struct asm_constraint { 55 pseudo_t pseudo; 56 const char *constraint; 57 const struct ident *ident; 58 }; 59 60 DECLARE_ALLOCATOR(asm_constraint); 61 DECLARE_PTR_LIST(asm_constraint_list, struct asm_constraint); 62 63 struct asm_rules { 64 struct asm_constraint_list *inputs; 65 struct asm_constraint_list *outputs; 66 struct asm_constraint_list *clobbers; 67 }; 68 69 DECLARE_ALLOCATOR(asm_rules); 70 71 struct instruction { 72 unsigned opcode:8, 73 size:24; 74 struct basic_block *bb; 75 struct position pos; 76 struct symbol *type; 77 union { 78 pseudo_t target; 79 pseudo_t cond; /* for branch and switch */ 80 }; 81 union { 82 struct /* entrypoint */ { 83 struct pseudo_list *arg_list; 84 }; 85 struct /* branch */ { 86 struct basic_block *bb_true, *bb_false; 87 }; 88 struct /* switch */ { 89 struct multijmp_list *multijmp_list; 90 }; 91 struct /* phi_node */ { 92 struct pseudo_list *phi_list; 93 }; 94 struct /* phi source */ { 95 pseudo_t phi_src; 96 struct instruction_list *phi_users; 97 }; 98 struct /* unops */ { 99 pseudo_t src; 100 struct symbol *orig_type; /* casts */ 101 unsigned int offset; /* memops */ 102 }; 103 struct /* binops and sel */ { 104 pseudo_t src1, src2, src3; 105 }; 106 struct /* slice */ { 107 pseudo_t base; 108 unsigned from, len; 109 }; 110 struct /* setval */ { 111 pseudo_t symbol; /* Subtle: same offset as "src" !! */ 112 struct expression *val; 113 }; 114 struct /* call */ { 115 pseudo_t func; 116 struct pseudo_list *arguments; 117 struct symbol *fntype; 118 }; 119 struct /* context */ { 120 int increment; 121 int check; 122 struct expression *context_expr; 123 }; 124 struct /* asm */ { 125 const char *string; 126 struct asm_rules *asm_rules; 127 }; 128 }; 129 }; 130 131 enum opcode { 132 OP_BADOP, 133 134 /* Entry */ 135 OP_ENTRY, 136 137 /* Terminator */ 138 OP_TERMINATOR, 139 OP_RET = OP_TERMINATOR, 140 OP_BR, 141 OP_CBR, 142 OP_SWITCH, 143 OP_INVOKE, 144 OP_COMPUTEDGOTO, 145 OP_UNWIND, 146 OP_TERMINATOR_END = OP_UNWIND, 147 148 /* Binary */ 149 OP_BINARY, 150 OP_ADD = OP_BINARY, 151 OP_SUB, 152 OP_MULU, OP_MULS, 153 OP_DIVU, OP_DIVS, 154 OP_MODU, OP_MODS, 155 OP_SHL, 156 OP_LSR, OP_ASR, 157 158 /* Logical */ 159 OP_AND, 160 OP_OR, 161 OP_XOR, 162 OP_AND_BOOL, 163 OP_OR_BOOL, 164 OP_BINARY_END = OP_OR_BOOL, 165 166 /* Binary comparison */ 167 OP_BINCMP, 168 OP_SET_EQ = OP_BINCMP, 169 OP_SET_NE, 170 OP_SET_LE, 171 OP_SET_GE, 172 OP_SET_LT, 173 OP_SET_GT, 174 OP_SET_B, 175 OP_SET_A, 176 OP_SET_BE, 177 OP_SET_AE, 178 OP_BINCMP_END = OP_SET_AE, 179 180 /* Uni */ 181 OP_NOT, 182 OP_NEG, 183 184 /* Select - three input values */ 185 OP_SEL, 186 187 /* Memory */ 188 OP_MALLOC, 189 OP_FREE, 190 OP_ALLOCA, 191 OP_LOAD, 192 OP_STORE, 193 OP_SETVAL, 194 OP_SYMADDR, 195 OP_GET_ELEMENT_PTR, 196 197 /* Other */ 198 OP_PHI, 199 OP_PHISOURCE, 200 OP_CAST, 201 OP_SCAST, 202 OP_FPCAST, 203 OP_PTRCAST, 204 OP_INLINED_CALL, 205 OP_CALL, 206 OP_VANEXT, 207 OP_VAARG, 208 OP_SLICE, 209 OP_SNOP, 210 OP_LNOP, 211 OP_NOP, 212 OP_DEATHNOTE, 213 OP_ASM, 214 215 /* Sparse tagging (line numbers, context, whatever) */ 216 OP_CONTEXT, 217 OP_RANGE, 218 219 /* Needed to translate SSA back to normal form */ 220 OP_COPY, 221 }; 222 223 struct basic_block_list; 224 struct instruction_list; 225 226 struct basic_block { 227 struct position pos; 228 unsigned long generation; 229 int context; 230 struct entrypoint *ep; 231 struct basic_block_list *parents; /* sources */ 232 struct basic_block_list *children; /* destinations */ 233 struct instruction_list *insns; /* Linear list of instructions */ 234 struct pseudo_list *needs, *defines; 235 union { 236 unsigned int nr; /* unique id for label's names */ 237 void *priv; 238 }; 239 }; 240 241 242 static inline void add_bb(struct basic_block_list **list, struct basic_block *bb) 243 { 244 add_ptr_list(list, bb); 245 } 246 247 static inline void add_instruction(struct instruction_list **list, struct instruction *insn) 248 { 249 add_ptr_list(list, insn); 250 } 251 252 static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp) 253 { 254 add_ptr_list(list, multijmp); 255 } 256 257 static inline pseudo_t *add_pseudo(struct pseudo_list **list, pseudo_t pseudo) 258 { 259 return add_ptr_list(list, pseudo); 260 } 261 262 static inline int remove_pseudo(struct pseudo_list **list, pseudo_t pseudo) 263 { 264 return delete_ptr_list_entry((struct ptr_list **)list, pseudo, 0) != 0; 265 } 266 267 static inline int bb_terminated(struct basic_block *bb) 268 { 269 struct instruction *insn; 270 if (!bb) 271 return 0; 272 insn = last_instruction(bb->insns); 273 return insn && insn->opcode >= OP_TERMINATOR 274 && insn->opcode <= OP_TERMINATOR_END; 275 } 276 277 static inline int bb_reachable(struct basic_block *bb) 278 { 279 return bb != NULL; 280 } 281 282 static inline void add_pseudo_ptr(pseudo_t *ptr, struct pseudo_ptr_list **list) 283 { 284 add_ptr_list(list, ptr); 285 } 286 287 static inline void add_pseudo_user_ptr(struct pseudo_user *user, struct pseudo_user_list **list) 288 { 289 add_ptr_list(list, user); 290 } 291 292 static inline int has_use_list(pseudo_t p) 293 { 294 return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_VAL); 295 } 296 297 static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp) 298 { 299 struct pseudo_user *user = __alloc_pseudo_user(0); 300 user->userp = pp; 301 user->insn = insn; 302 return user; 303 } 304 305 static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp) 306 { 307 *pp = p; 308 if (has_use_list(p)) 309 add_pseudo_user_ptr(alloc_pseudo_user(insn, pp), &p->users); 310 } 311 312 static inline void remove_bb_from_list(struct basic_block_list **list, struct basic_block *entry, int count) 313 { 314 delete_ptr_list_entry((struct ptr_list **)list, entry, count); 315 } 316 317 static inline void replace_bb_in_list(struct basic_block_list **list, 318 struct basic_block *old, struct basic_block *new, int count) 319 { 320 replace_ptr_list_entry((struct ptr_list **)list, old, new, count); 321 } 322 323 struct entrypoint { 324 struct symbol *name; 325 struct symbol_list *syms; 326 struct pseudo_list *accesses; 327 struct basic_block_list *bbs; 328 struct basic_block *active; 329 struct instruction *entry; 330 }; 331 332 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false); 333 extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target); 334 335 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size); 336 pseudo_t alloc_pseudo(struct instruction *def); 337 pseudo_t value_pseudo(struct symbol *type, long long val); 338 unsigned int value_size(long long value); 339 340 struct entrypoint *linearize_symbol(struct symbol *sym); 341 int unssa(struct entrypoint *ep); 342 void show_entry(struct entrypoint *ep); 343 const char *show_pseudo(pseudo_t pseudo); 344 void show_bb(struct basic_block *bb); 345 const char *show_instruction(struct instruction *insn); 346 347 #endif /* LINEARIZE_H */ 348 349