linearize.h

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