linearize.h

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