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