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 "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