1 #ifndef LINEARIZE_H 2 #define LINEARIZE_H 3 4 #include "lib.h" 5 #include "allocate.h" 6 #include "token.h" 7 #include "opcode.h" 8 #include "parse.h" 9 #include "symbol.h" 10 #include "ptrmap.h" 11 12 struct instruction; 13 14 struct pseudo_user { 15 struct instruction *insn; 16 pseudo_t *userp; 17 }; 18 19 DECLARE_ALLOCATOR(pseudo_user); 20 DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user); 21 DECLARE_PTRMAP(phi_map, struct symbol *, pseudo_t); 22 23 24 enum pseudo_type { 25 PSEUDO_VOID, 26 PSEUDO_UNDEF, 27 PSEUDO_REG, 28 PSEUDO_SYM, 29 PSEUDO_VAL, 30 PSEUDO_ARG, 31 PSEUDO_PHI, 32 }; 33 34 struct pseudo { 35 int nr; 36 enum pseudo_type type; 37 struct pseudo_user_list *users; 38 struct ident *ident; 39 union { 40 struct symbol *sym; 41 struct instruction *def; 42 long long value; 43 }; 44 void *priv; 45 }; 46 47 extern struct pseudo void_pseudo; 48 49 #define VOID (&void_pseudo) 50 51 static inline bool is_zero(pseudo_t pseudo) 52 { 53 return pseudo->type == PSEUDO_VAL && pseudo->value == 0; 54 } 55 56 static inline bool is_nonzero(pseudo_t pseudo) 57 { 58 return pseudo->type == PSEUDO_VAL && pseudo->value != 0; 59 } 60 61 62 struct multijmp { 63 struct basic_block *target; 64 long long begin, end; 65 }; 66 67 struct asm_constraint { 68 pseudo_t pseudo; 69 const char *constraint; 70 const struct ident *ident; 71 }; 72 73 DECLARE_ALLOCATOR(asm_constraint); 74 DECLARE_PTR_LIST(asm_constraint_list, struct asm_constraint); 75 76 struct asm_rules { 77 struct asm_constraint_list *inputs; 78 struct asm_constraint_list *outputs; 79 struct asm_constraint_list *clobbers; 80 }; 81 82 DECLARE_ALLOCATOR(asm_rules); 83 84 struct instruction { 85 unsigned opcode:7, 86 tainted:1, 87 size:24; 88 struct basic_block *bb; 89 struct position pos; 90 struct symbol *type; 91 pseudo_t target; 92 union { 93 struct /* entrypoint */ { 94 struct pseudo_list *arg_list; 95 }; 96 struct /* branch */ { 97 pseudo_t cond; 98 struct basic_block *bb_true, *bb_false; 99 }; 100 struct /* switch */ { 101 pseudo_t _cond; 102 struct multijmp_list *multijmp_list; 103 }; 104 struct /* phi_node */ { 105 pseudo_t phi_var; // used for SSA conversion 106 struct pseudo_list *phi_list; 107 unsigned int used:1; 108 }; 109 struct /* phi source */ { 110 pseudo_t phi_src; 111 struct instruction_list *phi_users; 112 }; 113 struct /* unops */ { 114 pseudo_t src; 115 struct symbol *orig_type; /* casts */ 116 }; 117 struct /* memops */ { 118 pseudo_t addr; /* alias .src */ 119 unsigned int offset; 120 unsigned int is_volatile:1; 121 }; 122 struct /* binops and sel */ { 123 pseudo_t src1, src2, src3; 124 }; 125 struct /* slice */ { 126 pseudo_t base; 127 unsigned from, len; 128 }; 129 struct /* setval */ { 130 struct expression *val; 131 }; 132 struct /* setfval */ { 133 long double fvalue; 134 }; 135 struct /* call */ { 136 pseudo_t func; 137 struct pseudo_list *arguments; 138 struct symbol_list *fntypes; 139 }; 140 struct /* context */ { 141 int increment; 142 int check; 143 struct expression *context_expr; 144 }; 145 struct /* asm */ { 146 const char *string; 147 struct asm_rules *asm_rules; 148 }; 149 }; 150 }; 151 152 struct basic_block_list; 153 struct instruction_list; 154 155 struct basic_block { 156 struct position pos; 157 unsigned long generation; 158 union { 159 int context; 160 int postorder_nr; /* postorder number */ 161 int dom_level; /* level in the dominance tree */ 162 }; 163 struct entrypoint *ep; 164 struct basic_block_list *parents; /* sources */ 165 struct basic_block_list *children; /* destinations */ 166 struct instruction_list *insns; /* Linear list of instructions */ 167 struct basic_block *idom; /* link to the immediate dominator */ 168 struct basic_block_list *doms; /* list of BB idominated by this one */ 169 struct phi_map *phi_map; 170 struct pseudo_list *needs, *defines; 171 union { 172 unsigned int nr; /* unique id for label's names */ 173 void *priv; 174 }; 175 }; 176 177 178 // 179 // return the opcode of the instruction defining ``SRC`` if existing 180 // and OP_BADOP if not. It also assigns the defining instruction 181 // to ``DEF``. 182 #define DEF_OPCODE(DEF, SRC) \ 183 (((SRC)->type == PSEUDO_REG && (DEF = (SRC)->def)) ? DEF->opcode : OP_BADOP) 184 185 186 static inline void add_bb(struct basic_block_list **list, struct basic_block *bb) 187 { 188 add_ptr_list(list, bb); 189 } 190 191 static inline void add_instruction(struct instruction_list **list, struct instruction *insn) 192 { 193 add_ptr_list(list, insn); 194 } 195 196 static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp) 197 { 198 add_ptr_list(list, multijmp); 199 } 200 201 static inline pseudo_t *add_pseudo(struct pseudo_list **list, pseudo_t pseudo) 202 { 203 return add_ptr_list(list, pseudo); 204 } 205 206 static inline int remove_pseudo(struct pseudo_list **list, pseudo_t pseudo) 207 { 208 return delete_ptr_list_entry((struct ptr_list **)list, pseudo, 0) != 0; 209 } 210 211 static inline int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo) 212 { 213 return lookup_ptr_list_entry((struct ptr_list *)list, pseudo); 214 } 215 216 static inline int bb_terminated(struct basic_block *bb) 217 { 218 struct instruction *insn; 219 if (!bb) 220 return 0; 221 insn = last_instruction(bb->insns); 222 return insn && insn->opcode >= OP_TERMINATOR 223 && insn->opcode <= OP_TERMINATOR_END; 224 } 225 226 static inline int bb_reachable(struct basic_block *bb) 227 { 228 return bb != NULL; 229 } 230 231 static inline int lookup_bb(struct basic_block_list *list, struct basic_block *bb) 232 { 233 return lookup_ptr_list_entry((struct ptr_list *)list, bb); 234 } 235 236 237 static inline void add_pseudo_user_ptr(struct pseudo_user *user, struct pseudo_user_list **list) 238 { 239 add_ptr_list(list, user); 240 } 241 242 static inline int has_use_list(pseudo_t p) 243 { 244 return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_UNDEF && p->type != PSEUDO_VAL); 245 } 246 247 static inline int pseudo_user_list_size(struct pseudo_user_list *list) 248 { 249 return ptr_list_size((struct ptr_list *)list); 250 } 251 252 static inline bool pseudo_user_list_empty(struct pseudo_user_list *list) 253 { 254 return ptr_list_empty((struct ptr_list *)list); 255 } 256 257 static inline int has_users(pseudo_t p) 258 { 259 return !pseudo_user_list_empty(p->users); 260 } 261 262 static inline bool multi_users(pseudo_t p) 263 { 264 return ptr_list_multiple((struct ptr_list *)(p->users)); 265 } 266 267 static inline int nbr_users(pseudo_t p) 268 { 269 return pseudo_user_list_size(p->users); 270 } 271 272 static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp) 273 { 274 struct pseudo_user *user = __alloc_pseudo_user(0); 275 user->userp = pp; 276 user->insn = insn; 277 return user; 278 } 279 280 static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp) 281 { 282 *pp = p; 283 if (has_use_list(p)) 284 add_pseudo_user_ptr(alloc_pseudo_user(insn, pp), &p->users); 285 } 286 287 static inline void remove_bb_from_list(struct basic_block_list **list, struct basic_block *entry, int count) 288 { 289 delete_ptr_list_entry((struct ptr_list **)list, entry, count); 290 } 291 292 static inline void replace_bb_in_list(struct basic_block_list **list, 293 struct basic_block *old, struct basic_block *new, int count) 294 { 295 replace_ptr_list_entry((struct ptr_list **)list, old, new, count); 296 } 297 298 struct entrypoint { 299 struct symbol *name; 300 struct symbol_list *syms; 301 struct pseudo_list *accesses; 302 struct basic_block_list *bbs; 303 struct basic_block *active; 304 struct instruction *entry; 305 unsigned int dom_levels; /* max levels in the dom tree */ 306 }; 307 308 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false); 309 extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target); 310 311 struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type); 312 struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident); 313 struct instruction *insert_phi_node(struct basic_block *bb, struct symbol *var); 314 void add_phi_node(struct basic_block *bb, struct instruction *phi_node); 315 316 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type); 317 pseudo_t alloc_pseudo(struct instruction *def); 318 pseudo_t value_pseudo(long long val); 319 pseudo_t undef_pseudo(void); 320 321 struct entrypoint *linearize_symbol(struct symbol *sym); 322 int unssa(struct entrypoint *ep); 323 void show_entry(struct entrypoint *ep); 324 const char *show_pseudo(pseudo_t pseudo); 325 void show_bb(struct basic_block *bb); 326 const char *show_instruction(struct instruction *insn); 327 const char *show_label(struct basic_block *bb); 328 329 #endif /* LINEARIZE_H */ 330 331