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